Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3748
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 i-th person in the army has an initial risk factor ai.
  • 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 i-th person's risk factor will become bi if one of his superior is controlled by Lelouch and Lelouch choose to command The i-th person.(ai may be smaller than bi.)
  • 4) Using Geass to someone is also dangerous, so to use Geass to the i-th person, there is a risk factor ci.

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 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≤mn, 0≤ai,bi,ci≤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