{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"**有n个洞穴编号为1~n,洞穴间有通道,形成了一个n-1条边的树, 洞穴的入口即根节点是1。\n每个洞穴有x只bugs,并有价值y的金子,全部消灭完一个洞穴的虫子,就可以获得这个洞穴的y个金子.\n现在要派m个战士去找金子,从入口进入。每次只有消灭完当前洞穴的所有虫子,才可以选择进入下一个洞穴。\n一个战士可以消灭20只虫子,如果要杀死x只虫子,那么要x/20向上取整即(x+19)/20个战士。\n如果要获得某个洞穴的金子,必须留下足够杀死所有虫子的战士数量, 即(x+19)/20个战士,然后这些留下战士就不能再去其它洞穴\n其他战士可以继续走去其它洞穴,可以选择分组去不同的洞穴。\n战士只能往洞穴深处走,不能走回头路\n问最多能获得多少金子?**"}},{"title":"Input","value":{"format":"MD","content":"The input contains several test cases. The first line of each test case contains two integers N (0 \u0026lt; N \u0026lt;\u003d 100) and M (0 \u0026lt;\u003d M \u0026lt;\u003d 100), which are the number of rooms in the cavern and the number of starship troopers you have, respectively. The following N lines give the description of the rooms. Each line contains two non-negative integers -- the amount of bugs inside and the possibility of containing a brain, respectively. The next N - 1 lines give the description of tunnels. Each tunnel is described by two integers, which are the indices of the two rooms it connects. Rooms are numbered from 1 and room 1 is the entrance to the cavern. \n\u003cbr\u003e \n\u003cbr\u003eThe last test case is followed by two -1\u0027s. \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"MD","content":"For each test case, print on a single line the maximum sum of all the possibilities of containing brains for the taken rooms. \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e5 10\n50 10\n40 10\n40 20\n65 30\n70 30\n1 2\n1 3\n2 4\n2 5\n1 1\n20 7\n-1 -1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003e50\n7\u003c/pre\u003e"}}]}