IOI '05 - Nowy Sacz, Poland

Rivers

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.

There are n lumberjacks' 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.

The king's 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.

Write a program that:

  • reads 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,
  • calculates the minimal cost of river transportation after building additional sawmills,
  • writes the result to the standard output.

Input

The first line of input contains two integers: n - the number of villages other than Bytetown (2 ≤ n ≤ 100), and k - the number of additional sawmills to be built (1 ≤ k ≤ 50 and k ≤ n). The villages are numbered 1, 2, …, n, while Bytetown has number 0.

Each of the following n lines contains three integers, separated by single spaces. Line i+1 contains:

  • wi - the number of trees cut near village i per year (0 ≤ wi ≤ 10 000),
  • vi - the first village (or Bytetown) downriver from village i (0 ≤ vi ≤ n),
  • di - the distance (in kilometres) by river from village i to vi (1 ≤ di ≤ 10 000).

It is guaranteed that the total cost of floating all the trees to the sawmill in Bytetown in one year does not exceed 2 000 000 000 cents.

In 50% of test cases n will not exceed 20.

Output

The first and only line of the output should contain one integer: the minimal cost of river transportation (in cents).

Sample Input

4 2
1 0 1
1 1 10
10 2 5
1 2 3

Sample Output

4

The above picture illustrates the example input data. Village numbers are given inside circles. Numbers below the circles represents the number of trees cut near villages. Numbers above the arrows represent rivers' lengths. The sawmills should be built in villages 2 and 3.

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 01, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...