Recently, the company of GUN bought a mountain land, and going to build N factories on the land. The location of every factory can be determined by a three-dimensional coordinate [x, y, h] (x, y represent the plane coordinates; h is the height).
Now, the company of GUN needs to supply water to every factory. So they built a water-supply source at [xw, yw, hw]. Every factory can get water from the water-supply source directly or from another factory which has already got water. Apparently, at most N water pipes are needed to guarantee every factory can get water. Notice: all the water that factories can get come from the water-supply source eventually. We need to know that it costs |x1 - x2| + |y1 - y2| + |h1 - h2| to buid a water pipe between [x1, y1, h1] and [x2, y2, h2]. Besides, because of some technical problem, if the height of a factory exceeds LIM, the factory must get water from the water-supply source directly (even so, the factory can also delivery water to other factories).
Our aim is to ensure that every factory have water suply and do our best to minimize the cost.
Firstly, there is a integer T indicate there are T test cases. ( 0 < T <= 20)
For each case, begin with a line contain a inerger N, which is the number of factories.(1 <= N <= 500).
The next N lines, each line contain 3 integers x, y, h, indicates the factory's location.
The last line contains 4 inergers LIM, xw, yw, hw, indicate the height limit and the coordinate of the water-supply source.
(0 <= x, y, h, LIM, xw, yw, hw <= 100000)
For each case, output one line, print the minimum cost.
2 2 3 10 7 2 5 9 10 1 20 3 2 3 4 7 2 3 6 5 3 10 2
hanchao717 & mario