321. Dream Coins

Problem Statement:
You won't believe what happened to Mohamed Ahmed - AKA Nesr, and TheSecretSleeper. One day some coins started to fall from the sky. Yes, I'm not lying! They just kept falling from the sky! And Mohamed Ahmed - luckily for him - was outdoors when this happened. Specifically, with his sharp eyes, he saw N coins. As these coins exist in our world (also known as three-dimensional space), each coin currently has X, Y, and Z coordinates, and each coin has a value V. Every second the Z coordinate of each coin would decrease by 1. So, Nesr had a basket. At any integer moment, if Nesr is at a point (X, Y), and a coin was at (X, Y, 1), the coin would enter the basket instantly, and he doesn't have to stand still during that or anything. Initially, Nesr can stand wherever you tell him (A true magician, isn't he?). Then he can walk or stand still between consecutive seconds. If he chooses to walk, he can choose to either change his X coordinate or Y coordinate by 1 (positively or negatively). So, I guess by now you can easily guess my goal. Find an optimal strategy with which Nesr can maximize the sum of values of coins that fall in his basket.

Input Format:
The input will start with an integer T which is the number of test cases where (1 ≤ T ≤ 100). Each test case start with a line with one integer, N (1 ≤ N ≤ 1, 000). Then follow N lines, each line has 4 integers representing X, Y, Z, and V of a coin, respectively. (0 ≤ X, Y, V ≤ 109), and (1 ≤ Z ≤ 109).

Output Format:
For each test case you should output "Case X: Y" where X is the case number starting from 1, and Y is maximum sum of values Nesr can get.

Sample Input:
1 4 70 58 88 52 5 38 84 95 35 27 68 3 21 68 98 18

Sample Output:
Case 1: 95

Notes:
Did I tell you that the whole above story is just a dream of Nesr during a session? I thought it was true because you can't tell if Nesr is actually sleeping or no.

 Added by: hossamyosef Added at: 2014-11-11 15:32:33 UTC Time Limit: 2 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2014