

Battle of SubmarinesTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 153 Accepted Submission(s): 22 Problem Description 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. Input 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 ith submarine; Si is the time the ith 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. Output For each test case, print a single line containing a number indicating the maximum sum. Sample Input
Sample Output
Source  
