Code Geass  Lelouch's Plan
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Lelouch Lamperouge, the Prince of Britannia, wants to take revenge on his father and the country, The Holy Empire Of Britannia. Through Britannia has strong army, Lelouch can use his amazing power, Code Geass, to help him win the battle. Now he wants to destroy the army in some place.
The army of Britannia has a hierarchy. There are several rules.

1) Each people has at most one direct superior which is also a superior.

2) One's superior's superior is also his superior.

3) If A is not B's direct superior or one of B's superiors' superior, then A can't be B's superior.
Lelouch's Geass can control anyone seeing his eyes. So he wants to use this power to beat the army. To analyze the feasibility of this action, he uses risk factor how dangerous the action is.

1) The ith person in the army has an initial risk factor a_{i}.

2) And if Lelouch choose to use Geass on someone, that person's risk factor will become zero and Lelouch can choose to let him command any of his subordinates(if has). If Lelouch does so, those subordinates will be influenced and their risk factor will change.

3) The ith person's risk factor will become b_{i} if one of his superior is controlled by Lelouch and Lelouch choose to command The ith person.(a_{i} may be smaller than b_{i}.)

4) Using Geass to someone is also dangerous, so to use Geass to the ith person, there is a risk factor c_{i}.
Using Geass too many times will make it lose control, so Lelouch decides to use Geass to control at most m people. Now Lelouch wants to know, what's the minimum of the risk factor of this action(which means the sum of everyone's risk factor). For he is busy taking care of Nunnally, he wants you, his allegiant and capable subordinate to solve this problem.
Input
At first there is an integer T, which is the number of cases.
Then there are T cases. In each case, the first line contains two integer n ,represents the number of people in the army, and m, represents the limitation of people Lelouch can use Geass to control.
Then there is n lines, the ith line contains four integers fa_{i}, a_{i}, b_{i}, c_{i}. fa_{i} is the index of the ith person's direct superior.(The index of people is from 1 to n, and it means this person doesn't have a direct superior here if fa_{i} equal to zero.) And a_{i}, b_{i}, c_{i} has mentioned above.
(T≤200, 1≤n≤200, 1≤m≤n, 0≤a_{i},b_{i},c_{i}≤1000)
Output
For each case, output an integer represents the minimum of the risk factor of the action.
Sample Input
2
5 3
0 5 3 10
0 2 2 2
1 2 6 4
1 5 2 1
2 6 1 3
7 2
7 10 4 2
7 0 0 5
6 8 4 5
1 3 1 5
1 6 2 4
2 7 3 9
0 2 2 8
Sample Output
11
19
Author:
ZHANG, Ruijie
Source:
ZOJ Monthly, January 2014
Submit
Status