提示: 欢迎访问OurACM平台。
Problem 1066 Battle of Stalingrad

Accept: 32    Submit: 65
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

May 9 this year, More than 50 heads of states or international organizations gathered on Moscow to commemorate the 60th anniversary of the end of World War II. Battle of Stalingrad from July to November in 1942 was the turning point in World War II. Soviets troops used bazooka in this battle first time, and made good execution for heinie. For there having a Russian letter "K" in the bazooka, soviet soldiers named the bazooka Katyusha rocket. The theory of Katyusha rocket is that a group rockets is fired at the same area, in order to make dense blast and good execution swiftly.

Suppose that you can manipulate a Katyusha rocket, which can be moved westward or eastward, to assault the enemy in the northern area. Commander has numbered each kind of enemy objects (soldier, armored car, tank etc.). The higher of an object value is, the greater number the object has. The attack is carried out in the following way:

1. Katyusha rocket can only move eastward or westward along x axes.
2. Given the cannon-shot and the blast radius of the bazooka each time, you must choose a launch position where you can destroy enemy objects with the total value as high as possible.
3. Katyusha rocket can only be fired northward.
4. The radius of bombsite is r. All objects within bombsite will be destroyed.
5. At the moment that a few bombsites include the same total value of enemy objects, exterminate the west objects first.

Input

The first line of the input is an integer n (0<n<100), and the following lines are the data of n test cases. For each case, the first line contains an integer x (0<x<=10000), which is followed by x lines data. Each line consists of three integers a (0<a<=100), b (0<b<=100), c (0<c<=100), where (a, b) and c denote the coordinate and the number of an enemy object respectively. Then there is a line containing an integer y, which is followed by y lines. Each line consists of two integers, where the first integer is d (0<d<100) and the second is r (0<r<100), denoting the given cannon-shot and the blast radius of the rocket each time. There is one space between every two integers in a line.

Output

For each test case, output a line containing an integer representing the highest total value of the destroyed enemy objects.

Sample Input

1 7 2 3 3 5 6 2 6 7 8 6 4 5 3 6 2 7 4 4 2 7 8 2 6 1 4 2

Sample Output

21

Source

FJNUPC 2005

Submit  Back  Status  Discuss