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.
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.
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.
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 i-th line contains four integers fai, ai, bi, ci. fai is the index of the i-th 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 fai equal to zero.) And ai, bi, ci has mentioned above.
(T≤200, 1≤n≤200, 1≤m≤n, 0≤ai,bi,ci≤1000)
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