Battle of Submarines

A ship is on a W wide sea area. N enemy submarines numbered from 1 to N are underwater moving from west to east at
depth of D. Every two seconds the submarine can move one unit distance. The ship is equipped with unlimited bombs.
At each second, the ship can do one of the following actions:
1. Move one unit.
2. Release a bomb, and destroy the first submarine vertically under the ship.
3. Do nothing.

At first, the ship's moving direction is from west to east. It changes its moving direction if and only if the bomb destroys a
special type of submarine.

At no time can submarines overlap at each other.



Every submarine has an important degree. Given the time each submarine enters the sea area at the most west side, and
whether the submarine is the special type, please calculate the maximum sum of destroyed submarines' important degree in
time [0, S] inclusive.

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

The input consists of several test cases. Each test case starts with a line containing four integers W, D, N, and S. Each of
the following N lines contains four integers: Gi, Si, Di, Ci. Gi indicates the important degree of i-th submarine; Si is the
time the i-th enters the sea area at the most west side; Di is the submarine's depth. If Ci is 1 then the submarine is the
special type, otherwise it is a normal one.

[Technical Specification]
T is an integer, and T <= 50.
W, D are integers, and 1 <= W, D <= 3.
N is an integer, and 1 <= N <= 30.
S is an integer, and 1 <= S <= 30.
Gi is an integer, and -1000 <= Gi <= 1000.
Si is an integer, and 0 <= Si <= S,
Di is an integer, and 1 <= Di <= D.
Ci is an integer, and Ci = 0 or 1.

For each test case, print a single line containing a number indicating the maximum sum.

2 
3 3 4 3 
10 1 1 0 
10 1 2 0 
10 1 3 0 
50 3 3 0 
3 3 2 3 
10 3 1 0 
-10 0 1 0 

70 
10 

The 4th Baidu Cup Central China Invitational Programming Contest