{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"MD","content":"Nearly all of the Kingdom of Byteland is covered by forests and rivers. Small rivers meet to form bigger rivers, which also meet and, in the end, all the rivers flow together into one big river. The big river meets the sea near Bytetown.\n\nThere are $n$ lumberjacks\u0027 villages in Byteland, each placed near a river. Currently, there is a big sawmill in Bytetown that processes all trees cut in the Kingdom. The trees float from the villages down the rivers to the sawmill in Bytetown. The king of Byteland decided to build $k$ additional sawmills in villages to reduce the cost of transporting the trees downriver. After building the sawmills, the trees need not float to Bytetown, but can be processed in the first sawmill they encounter downriver. Obviously, the trees cut near a village with a sawmill need not be transported by river. It should be noted that the rivers in Byteland do not fork. Therefore, for each village, there is a unique way downriver from the village to Bytetown.\n\nThe king\u0027s accountants calculated how many trees are cut by each village per year. You must decide where to build the sawmills to minimize the total cost of transporting the trees per year. River transportation costs one cent per kilometre, per tree."}},{"title":"Input","value":{"format":"MD","content":"The first line of input contains two integers: $n$ - the number of villages other than Bytetown ($2\\le n\\le 100$), and $k$ - the number of additional sawmills to be built ($1\\le k\\le n, k\\le 50$). The villages are numbered $1,2,\\ldots,n$, while Bytetown has number $0$.\n\nEach of the following lines contains three integers, separated by single spaces. Line $i+1$ contains:\n- $w_i$ - the number of trees cut near village $i$ per year ($0\\le w_i\\le 10000$),\n- $v_i$ - the first village (or Bytetown) downriver from village $i$ ($0\\le v_i\\le n$),\n- $d_i$ - the distance (in kilometres) by river from village $i$ to $v_i$ ($1\\le d_i\\le 10000$).\n\nIt is guaranteed that the total cost of floating all the trees to the sawmill in Bytetown in one year does not exceed $2\\times 10^9$ cents.\n\nIn 50% of test cases $n$ will not exceed $20$."}},{"title":"Output","value":{"format":"MD","content":" \u003cp\u003eThe first and only line of the output should contain one integer: the minimal cost of river transportation (in cents).\u003c/p\u003e "}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2\n1 0 1\n1 1 10\n10 2 5\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"MD","content":" \u003cdiv style\u003d\"max-width: 100%; height: 274; max-height: 274; width: 274; text-align: center;\"\u003e\n \u003cimg height\u003d\"274\" src\u003d\"CDN_BASE_URL/58912e6bd5f13b2b8eaad86fcb66f19a?v\u003d1659628728\" width\u003d\"379\"\u003e\n \u003c/div\u003e\n\n$\\text{}$\nThe above picture illustrates the example input data. Village numbers are given inside circles. Numbers below the circles represent the number of trees cut near villages. Numbers above the arrows represent rivers\u0027 lengths.\n\nThe sawmills should be built in villages $2$ and $3$."}}]}