SPACESHIP - Spaceship

no tags 

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

hide comments
smso: 2018-11-05 03:57:26

search space is small so brute-force method works

ALi Ibrahim: 2016-05-31 20:49:41

Nice problem, i recommend you to try it :D

Fionsel: 2016-05-30 22:01:29

In a normal world the distance would be less going directly to shop 2 instead of first stopping at shop 0. However in a normal world the distance is measured by taking the square root of (X1-X2)^2 + (Y1-Y2)^2 + (Z1-Z2)^2. So although the supplied example is correct, it is counter intuitive

coppercandle: 2016-05-04 18:53:23

@gnipod @nightwolf_9197 Going from the initial position to shop 0 requires a navigation cost of (60-0)^2 + (34-0)^2+(56-0)^2 = 7892. Going from shop 0 to shop 2 requires a navigation cost of (60-24)^2 + (61-34)^2 + (81-56)^2 = 2650. The goal is to minimize the navigation cost, not to minimize the number of shops visited.

Fendy: 2016-05-04 04:49:03

is this problem got no tc? :\ I submitted empty code and still got AC

nightwolf_9197: 2016-05-01 09:54:33

@coppercandle: But shop 2 already has enough mi,ki,ci why go to shop 0

gnipod: 2016-05-01 02:41:11

@coppercandle No shops cost 10542 :D

coppercandle: 2016-04-30 17:30:42

@gnipod One could go to shop 0 to shop 2 (0-based) for a navigation cost of 10542. :)

gnipod: 2016-04-30 02:41:26

case 2 output 10858


Added by:WhipppedCream
Date:2016-04-29
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:The 9th Thailand Olympiad in Informatics