### 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:

*w*_{i}- the number of trees cut near village*i*per year (0 ≤*w*_{i}≤ 10 000),*v*_{i}- the first village (or Bytetown) downriver from village*i*(0 ≤*v*_{i}≤*n*),*d*_{i}- the distance (in kilometres) by river from village*i*to*v*_{i}(1 ≤*d*_{i}≤ 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 Input4 2 1 0 1 1 1 10 10 2 5 1 2 3 ## Sample Output4 |

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...