In the future world, you have moved into the space colony, and will be using a flying disc which moves in three dimensions as a vehicle. You have been assigned with buying the parts to form 'N' sets of computer from the shops in the colony. Each set of computer consists of 3 parts: monitor, keyboard, and CPU. Because the parts available at one shop may not be enough for the 'N' computers and the budget is limited, you have to design a navigation system for the flying disc such that the total cost of navigation is minimized. You know the exact coordinates of the 'M' available shops and the number of the parts available at each store. Assume that the route from a shop to every other shop will have no obstacles, thus a straight path is always possible, the flying disc contains unlimited storage space, and the parts at each store are free. Let the trip terminate when all parts needed are collected. 

Let shop/position A has coordinate (X1, Y1, Z1) and shop/position B has coordinate (X2, Y2, Z2), the navigation cost between the two shops/positions is calculated by the formula (X1-X2)^2 + (Y1-Y2)^2 + (Z1-Z2)^2.

Input

The first line contains the integer 'N': the number of the required sets of computer.

The second line contains three integers 'X', 'Y', 'Z': the initial position of the spaceship in the form of coordinates (X, Y, Z)

The third line contains the integer 'M': the total number of shops in the colony

There follows 2M lines: the information for each shop in the colony, where two lines are responsible for the information of one shop.

The first of these two lines contains three integers 'Xi', 'Yi', 'Zi', the position of the shop in the form of coordinates (X, Y, Z)

The second of these two lines contains three integers 'Mi', 'Ki', 'Ci', the number of monitors, keyboards, and CPUs, respectively, available at the shop.

It is guaranteed that it is sufficient to build 'N' sets of computers from all parts of every shop combined.

Output

One line containing the minimum navigation cost from the initial position to the end of the trip.

Constraints

1 <= 'N' <= 20

0 <= 'X', 'Y', 'Z', 'Xi', 'Yi', 'Zi' <= 500

1 <= 'M' <= 10

0 <= 'Mi', 'Ki', 'Ci' <= 20

Example

Input #1:
1
0 0 0
2
10 0 0
2 5 7
0 10 0
0 3 9

Output #1:
100

Input #2:
5
0 0 0
5
60 34 56
0 5 7
90 41 92
1 7 8
24 61 81
6 8 8
41 86 70
5 6 7
46 97 85 
9 2 4

Output #2:
10542