There are 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 while the -th jewel is at initially. You can salvage one jewel immediately(regardless of other jewels wherever they are) with strength 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 -th jewel, it will be at after seconds. So you want to know the minimum possible total strength to salvage all the jewels.

The first line contains one integer , denoting the number of jewels.

Following  lines each contains four integers , 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  currently with strength .
* At the 1st second, we can salvage the second jewel which is at  currently with strength .
* At the 2nd second, we can salvage the first jewel which is at  currently with strength .

So the total strength is .