5394: Jewels

There are n jewels under the sea, and you want to salvage all the jewels. Image that the sea is a 3D coordinate system, and that you are at (0,0,0) while the i -th jewel is at (xi,yi,zi) initially. You can salvage one jewel immediately(regardless of other jewels wherever they are) with strength d^2 at every non-negative integer moment where d denotes the distance between you and the jewel you salvage at that moment. However, the jewels sink. Specifically, for the i -th jewel, it will be at (xi,yi,zi+t×vi) after t seconds. So you want to know the minimum possible total strength to salvage all the jewels.

The first line contains one integer n (1≤n≤300), denoting the number of jewels.Following n lines each contains four integers xi,yi,zi,vi (0≤∣xi∣,∣yi∣,zi,vi≤1000) denoting the jewels' initial positions and sinking velocities.

Output one line containing one integer, denoting the minimum possible total strength to salvage all the jewels.

3
1 1 1 1
2 2 2 2
3 3 3 3

62

One possible scheme to achive the minimum cost strength:
* At the 0th second, we can salvage the third jewel which is at (3,3,3)currently with strength 27.
* At the 1st second, we can salvage the second jewel which is at (2,2,4) currently with strength 24.
* At the 2nd second, we can salvage the first jewel which is at (1,1,3) currently with strength 11.
So the total strength is 27+24+11=62