一天，小B带着橡皮泥在田间走着，忽然他看到一个羊圈和一些三尺高的草。他于是好奇地往草里面走，突然小B一脚踏空，到了一个地下洞穴里面。
小B举目望去，发现这是一个迷宫，墙上挂着地图，揭示了迷宫的结构是树状的，总共有n间房间，每片叶结点都有一条通往外界的道路。然而小B又在迷宫里发现了一只史莱姆。
不幸的是，史莱姆也发现了他。小B于是打算跑路。
同时，史莱姆跑得比他快，于是小B打算在地上粘橡皮泥来减慢史莱姆的速度。迷宫的每一间屋子都有一定量的橡皮泥，且有一定的橡皮泥亲和度。在橡皮泥亲和度为x的地板上粘质量为y的橡皮泥可以困住史莱姆x*y的时间。
由于小B十分害怕，他不打算走回头路，同时小B只能携带质量为m的橡皮泥。
若不考虑小B中途被史莱姆追上的情况，求小B最多能困住史莱姆多久时间。
第一行两个整数n,m。
第二行至第n+1行，每行两个整数，分别代表该房间橡皮泥亲和度qi和该房间所有的橡皮泥的质量mi。
第n+2行至第2n行，每行两个整数xi,yi，表示xi和yi间有一条无向边相连。
输入数据保证所有边成一颗树。
一行一个数，表示小B最多能困住史莱姆的时间。
对于10%的数据，$1<n,m<10$。
对于50%的数据，$1<n,m<100$。
对于100%的数据，$1<n,m<1000$。保证所有的$qi<{10}^6$。