Description

Almost the entire kingdom of Byteland is covered with forests and rivers. Small rivers merge into slightly larger ones. In this way, all river water converges into a single large river, which eventually flows into the sea. At the mouth of this large river lies a village called Bytetown.

In Byteland, there are $n$ logging villages located along the rivers. There is currently a large sawmill in Bytetown that processes all the timber cut nationwide. Timber is cut and transported downstream along the rivers to the sawmill in Bytetown. The King of Byteland has decided to reduce transportation costs by building $k$ additional sawmills in other villages. After these sawmills are built, timber no longer needs to be sent all the way to Bytetown; it can be processed at the first new sawmill encountered during transport. Clearly, if a sawmill is located in a village, that village pays no transportation cost for its own timber; it can be processed locally.

Note: The rivers never split; they form a tree whose root is Bytetown.

The ministers have calculated the annual timber production of each village. Your task is to decide in which villages to build the sawmills to minimize the transportation cost. The cost is calculated as 1 cent per kilometer per ton of timber.

Input Format

The first line contains two integers $n, k$. Here $n$ is the number of villages, and $k$ is the number of sawmills to build. All villages other than Bytetown are named $1, 2, 3, \ldots, n$, and Bytetown is named $0$.

Lines $2$ through $(n + 1)$ each contain three integers. On the $(i + 1)$-th line, the integers are:

• $w_i$: the amount of timber produced annually by village $i$ (in tons),
• $v_i$: the nearest downstream village from $i$ (i.e., the parent of village $i$),
• $d_i$: the distance from $v_i$ to $i$ (in kilometers).

Output Format

Output the minimum total cost, in cents.

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

4

Hint

• Constraints:
  • For $50\%$ of the testdata, $n \le 20$.
  • For $100\%$ of the testdata, $2 \le n \le 100$, $1 \le k \le \min(n, 50)$, $0 \le v_i \le n$, $0 \le w_i \le 10^4$, $1 \le d_i \le 10^4$.
  • It is guaranteed that the annual cost of sending all timber to Bytetown does not exceed $2 \times 10^9$ cents.

Translated by ChatGPT 5