{"trustable":true,"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":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003cp\u003eNearly 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.\u003c/p\u003e\n\u003cp\u003eThere are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e 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 \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.211ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~k~\u003c/span\u003e\u003c/span\u003e 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.\u003c/p\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003ch4\u003eTask\u003c/h4\u003e\n\u003cp\u003eWrite a program that:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003ereads from the standard input the number of villages, the number of additional sawmills to be built, the number of trees cut near each village, and descriptions of the rivers,\u003c/li\u003e\n\u003cli\u003ecalculates the minimal cost of river transportation after building additional sawmills,\u003c/li\u003e\n\u003cli\u003ewrites the result to the standard output.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThe first line of input contains two integers: \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e — the number of villages other than Bytetown (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/1d97b1c53dfa86b7a92a5f85e0909f9b?v\u003d1715916022\" style\u003d\"vertical-align: -0.505ex; width:12.242ex; height:2.343ex;\" alt\u003d\"2 \\le n \\le 100\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le n \\le 100~\u003c/span\u003e\u003c/span\u003e), and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.211ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~k~\u003c/span\u003e\u003c/span\u003e — the number of additional sawmills to be built (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0c8631e8cb0a36dff9ec47d7de03361c?v\u003d1715916022\" style\u003d\"vertical-align: -0.505ex; width:10.896ex; height:2.343ex;\" alt\u003d\"1 \\le k \\le 50\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le k \\le 50~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/142b79b21c2f791591f9e5d47e5e281e?v\u003d1715916022\" style\u003d\"vertical-align: -0.505ex; width:5.705ex; height:2.343ex;\" alt\u003d\"k \\le n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~k \\le n~\u003c/span\u003e\u003c/span\u003e). The villages are numbered \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/3129edf73efc9f3df9df930747e6b5f8?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:9.932ex; height:2.509ex;\" alt\u003d\"1, 2, \\dots, n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1, 2, \\dots, n~\u003c/span\u003e\u003c/span\u003e, while Bytetown has number \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eEach of the following \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e lines contains three integers, separated by single spaces. Line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2f8acbbac7786e8d5e63adb3b6722209?v\u003d1715916022\" style\u003d\"vertical-align: -0.505ex; width:4.805ex; height:2.343ex;\" alt\u003d\"i + 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i + 1~\u003c/span\u003e\u003c/span\u003e contains:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/52d02a6d9edb27bee84c5605dd05eab3?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:2.464ex; height:2.009ex;\" alt\u003d\"w_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~w_i~\u003c/span\u003e\u003c/span\u003e — the number of trees cut near village \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e per year (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/027fc043e69515814296f4416bd56185?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:16.023ex; height:2.509ex;\" alt\u003d\"0 \\le w_i \\le 10\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le w_i \\le 10\\,000~\u003c/span\u003e\u003c/span\u003e),\u003c/li\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5c803c73a0e177916dca33b858a90d60?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:1.927ex; height:2.009ex;\" alt\u003d\"v_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~v_i~\u003c/span\u003e\u003c/span\u003e — the first village (or Bytetown) downriver from village \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0d91644a3d16445401a85ab24195e9b3?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:10.682ex; height:2.509ex;\" alt\u003d\"0 \\le v_i \\le n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le v_i \\le n~\u003c/span\u003e\u003c/span\u003e),\u003c/li\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d4cb32b4b2b74a0f0015831e739ef4b5?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:2.009ex; height:2.509ex;\" alt\u003d\"d_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~d_i~\u003c/span\u003e\u003c/span\u003e — the distance (in kilometres) by river from village \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e to \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5c803c73a0e177916dca33b858a90d60?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:1.927ex; height:2.009ex;\" alt\u003d\"v_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~v_i~\u003c/span\u003e\u003c/span\u003e (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/29e38511ec3a10f9030d6327150ebc2d?v\u003d1715916022\" style\u003d\"vertical-align: -0.671ex; width:15.568ex; height:2.509ex;\" alt\u003d\"1 \\le d_i \\le 10\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le d_i \\le 10\\,000~\u003c/span\u003e\u003c/span\u003e).\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIt is guaranteed that the total cost of floating all the trees to the sawmill in Bytetown in one year does not exceed \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2d72e4b953e7ab0c222f411869b60f79?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:12.786ex; height:2.176ex;\" alt\u003d\"2\\,000\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2\\,000\\,000\\,000~\u003c/span\u003e\u003c/span\u003e cents.\u003c/p\u003e\n\u003cp\u003eIn \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d345add568b987fff4d22bd0b5781a7d?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:4.261ex; height:2.343ex;\" alt\u003d\"50\\%\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~50\\%~\u003c/span\u003e\u003c/span\u003e of test cases \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e will not exceed \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/300ead7f8aa7ceb0318f9280015eb55b?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"20\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~20~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eThe first and only line of the output should contain one integer: the minimal cost of river transportation (in cents).\u003c/p\u003e\n\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\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\n\u003ch4\u003eExplanation for Sample Output\u003c/h4\u003e\n\u003cdiv style\u003d\"max-width: 100%;height: 274;max-height: 274;width: 379;text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/58912e6bd5f13b2b8eaad86fcb66f19a?v\u003d1715916022\" class\u003d\"tex-full\" width\u003d\"379\" height\u003d\"274\"\u003e\u003c/div\u003e\u003cp\u003eThe above picture illustrates the example input data. Village numbers are given inside circles. Numbers\nbelow the circles represent the number of trees cut near villages. Numbers above the arrows represent\nrivers\u0027 lengths.\u003c/p\u003e\n\u003cp\u003eThe sawmills should be built in villages \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/edff4a53ceab26bbeb9fa3434bd9765d?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/86748ce269b76185f219ba13eeede716?v\u003d1715916022\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"3\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~3~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}