题目背景

膜拜传奇特级大师劲哥哥，今日在 $\text{NOI}$ 铜牌获奖名单上称您为七中育才尊贵的大名，一股敬佩油然而生，您在 $\text{NOI}$ 为校争光，扬我育才威名，向您上献最真挚的膜拜！

问题描述

给你一棵 $n$ 个点的树，每个点有权值 $x,y$。在树上选择一个点集 $S$，在点集 $S$ 连通，并且 $\lvert S \rvert=m$ 的前提下，最小化

$$(\sum_{i\in S} x_i)\times (\sum_{i\in S}y_i)$$

输入格式

第一行，两个正整数 $n,m$。 接下来 $n$ 行，每行两个正整数 $x_i,y_i$。 接下来 $n − 1$ 行，每行两个数 $u, v$，表示树上的一条边 $(u, v)$。

输出格式

一行，一个整数表示答案。

样例 1 输入

5 3
3 2
5 2
1 2
1 5
2 3
1 2
1 4
2 3
2 5

样例 1 输出

54

数据规模与约定

$Subtask1$：$m = n − 1,10 pts$

$Subtask2$：$n ≤ 20,15 pts$

$Subtask3$：$x = 1,25 pts$

$Subtask4$：无特殊限制，$50 pts$，依赖于 $Subtask 1,2,3$

对于所有数据，保证有 $1 ≤ m ≤ n ≤ 2333$，保证 $0 ≤ x, y ≤ 2333$