提示: 欢迎访问OurACM平台。
Problem 1667 Rainbow Islands

Accept: 31    Submit: 120
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Rainbow Islands is an amusement park and is very beautiful.
Today is the birthday of the princess of the island. So there is a significant celebration in the island.
There is a kind of airship that can fly in the island.
The princess lives in a castle in the island.
To celebrate the birthday of the princess, there is an interesting game.
The game is as follows:
  • The Rainbow Islands can be modeled as three-dimensional coordinate system. So we can use (x, y, z) to represent the map of the island.
  • Three-dimensional system is a geometric model of the physical universe in which we live. The three dimensions are commonly called length, width, and depth (or height).
  • There are some boxes in the sky.
  • Each box is located in different position and has some value.
  • Every people in the island can participate into the game. The one who uses airship to gain the most value and arrives at the princess’s castle will gain the princess’s present.
  • Every time the people in the airship can move east, south, west, north or stay still. But the airship will ascend one unit.
  • The start position is (0, 0, 0).

Input

There are multiply test cases. For each test case, the first line is an integer N(0≤N≤500), indicating the number of boxes. Following N lines, each line contains four integers x, y, z, v(-200≤x≤200, -200≤y≤200,0≤z≤4000,0 < v≤250), indicating the position of the box and the value of the box. The last line contains three integers sx, sy, sz(-200≤sx≤200, -200≤sy≤200,0≤sz≤4000), indicating the position of the princess’s castle. The positions are all different.

Output

For each test case, output an integer which is the maximum value you can gain in the game if you can arrive at the princess’s castle finally. If you can’t arrive at the princess’s castle, just output “-1”.

Sample Input

1 1 1 2 200 3 3 10 1 1 1 3 200 10 10 10 1 1 0 0 100 1 0 1

Sample Output

200 -1 0

Hint

In the third sample, you can not gain the value of box in the position (1, 0, 0) because the airship can only arrive at one of the four positions (1, 0, 1), (-1, 0, 1), (0, 1, 1), (0, -1, 1) next time.

Source

FOJ月赛-2008年11月

Submit  Back  Status  Discuss