You are the director of sales of the Moroccan Cyber-security and Privacy Company, a global leader in web security and privacy protection. Your company works with governments and international IT firms to provide more secure web applications.

Like any other director in a large company, your time schedule is overcrowded with meetings. Your assistant has scheduled \(N\) meetings with \(N\) different companies, for each meeting she noted the type of the meeting, the date of the meeting, its duration and the profit your company will make after you attend it. Of course, you can't attend all of them, so you have to choose which meeting you are going to hold in order to maximize the total profit your company gets. You cannot attend more than one meeting on the same day, and you cannot make two consecutive meetings of the same type, but you can ask your assistant to change the type of any meeting. You can do that at most \(k\) times.

Input Specification

The input consists of multiple test cases, the first line of the input contains an integer \(T\) denoting the number of them.

Each test case starts with one line containing two integers \(N\) and \(k\) described above \((0 \leq k \leq 10\), \(1\leq N \leq 10^5\) and \(k \leq N\)).

Each one of the next \(N\) lines contains \(4\) integers : \(S_i\),\(D_i\),\(P_i\) and \(T_i\) denoting respectively the day when meeting \(i\) is going to be held, the duration of this meeting in days, the profit you get after attending the meeting and the type of the meeting (\(1\leq S_i,D_i,P_i \leq 10^9\) and \(1 \leq T_i \leq 3\)).

Output Specification

For each test case output one integer, the maximum profit your company gets.

Scoring

• \(Si,Di,Pi \leq 1000\), \(T_i = 1, k = 0\) and \( N \leq 10\) (10 points).
• All \(P_i\) are equal (15 points).
• \(N \leq 1000\) (15 points).
• \(k = 0\) (20 points).
• No additional constraints (40 point).

Sample Input

2
4 3
1 1 10 1
2 10 100 2
3 1 40 3
4 1 40 1
5 1
1 1 10 1
2 2 100 1
3 1 40 3
4 2 40 1
5 2 30 1

Sample Output

110
150