Jiahai the Potato has baked his famous shepherd's pie filled with the best potatoes from his potato farm. His shepherd's pie is in the shape of a rectangle with height H units and width W units. In order to evenly split the potatoes, he cuts up his potatoes into very small pieces and marks the unit lattice points on his pie with coordinates from (0,0) to (W,H) inclusive. He then randomly picks lattice points and stuffs pieces of potatoes into those spots.
Rar the Cat, however, is jealous of how good Jiahai the Potato can bake his pie and wants to sabotage his pie. He decides to stuff pieces of rotten potatoes into the spots marked by the lattice points. After that, the hungry Mr. Panda would like to take a slice of the pie. He finds a pie cutter in the shape of an isosceles right angled triangle whose sides are slightly longer than L units. To maximise the number of potatoes he gets, he wants to cut a piece of pie with the maximum possible number of lattice points. However, he also smells the rotten potatoes and so would like to maximise the value of (number of good potatoes - number of rotten potatoes). Help Mr. Panda find all the slices that maximise his satisfaction.
The first line of input will contain 3 integers, H,W,L separated by spaces where 1 ≤ L ≤ min(H,W)
The next line will contain an integer P and the next P lines will each contain 3 integers X,Y,N meaning that Jiahai the Potato puts N good potatoes into the spot on the pie marked by the lattice point (X,Y). The coordinate is guaranteed to be a valid lattice point between (0,0) and (W,H).
The next line will contain an integer R and the next R lines will each contain 3 integers X,Y,N meaning that Rar the Cat puts N rotten potatoes into the spot on the pie marked by the lattice point (X,Y). The coordinate is guaranteed to be a valid lattice point between (0,0) and (W,H).
If the maximum score as described above is non-negative, output two integers separated by a space. The first integer is the maximum score and the second is the number of possible slices Mr. Panda can cut. Two slices are different if at least one lattice point is only in one of the slices and the slices can overlap.
If the maximum score is negative, output on a single line "NO PIE :(" without the quotes.
For all lines in the input, N will fit into a 32-bit signed integer.
Subtask 1 (10%): 1 ≤ H,W ≤ 10, 0 ≤ P,R ≤ 1000
Subtask 2 (30%): 1 ≤ H,W ≤ 500, 0 ≤ P,R ≤ 100000
Subtask 3 (60%): 1 ≤ H,W ≤ 1000, 0 ≤ P,R ≤ 1000000
Subtask 4 (0%) : Sample test cases
1 2 1 5 0 0 1 0 1 1 1 0 1 1 1 1 2 1 1 2 2 0 5 2 0 5
Using the typical Cartesian coordinate system with the bottom left-hand corner as (0,0), the marked points are the ones with good potatoes and the unmarked point only has bad potatoes so clearly we only want slices with 3 good potato pieces as the maximum. The diagram shows 2 possible cuttings and it should not be difficult to figure out that there are a total of 5 possible cuttings.