Fax McClad, Croneria's most powerful bounty hunter, has been hired by the government to defend a planet that contains important government secrets.

One day, Fax wakes up to see a huge fleet of ~N~ Space Pirate ships approaching the planet! The Space Pirate ships can be represented as 2-D objects on a plane. The ~i^\text{th}~ Space Pirate ship's center is located at lattice (integer) point ~(x_i,y_i)~, has a "corner radius" of ~r_i~, and requires ~e_i~ energy to destroy. A point is within a Space Pirate ship's area if the Manhattan distance between the point and the ship's center is no greater than its corner radius ~r_i~.

Space Pirate ships have another special property. If one ship is destroyed, all other ships that are touching it or another affected ship, even at a point, will take damage equal to the energy required to destroy the destroyed ship. Thus, the energy required to destroy the other ships will decrease by this amount. Other ships that are destroyed by this process do not incur additional damage to surrounding ships.

For instance, if ship ~A~ touches ship ~B~ and ship ~B~ touches ship ~C~, when ship ~A~ is destroyed, both ship ~B~ and ship ~C~ take damage. Also, when a ship is destroyed, it still exists as junk and can still connect to other ships. In the same example, if instead ship ~B~ is destroyed first, followed by ship ~A~, ship ~C~ is damaged both times.

However, energy is a limited and valuable resource. Therefore, Fax would like to know the minimum amount of energy required to destroy all of the Space Pirate ships. Can you help him?

Constraints

For all subtasks:

~-10^9 \le x_i, y_i \le 10^9~

~1 \le r_i \le 10^9~

~1 \le e_i \le 1\,000~

Subtask 1 [5%]

~1 \le N \le 5~

Subtask 2 [15%]

~1 \le N \le 1\,000~

Subtask 3 [80%]

~1 \le N \le 100\,000~

Input Specification

The first line of input will consist of the integer ~N~.

~N~ lines of input follow. The ~i^\text{th}~ line will contain four space-separated integers, ~x_i~, ~y_i~, ~r_i~, and ~e_i~.

Output Specification

A single integer – the minimum amount of energy required in order to destroy all of the ships.

Sample Input 1

4
1 1 2 10
2 3 1 2
3 1 1 5
-2 1 1 7

Sample Output 1

10

Explanation for Sample Output 1

Fax can first destroy the 2nd ship, causing 2 damage to every ship, since they are all connected. Fax can then destroy the 4th ship, causing 5 damage to every ship, and thus also destroying the 3rd ship in the process. Finally, Fax can destroy the 1st ship. The total energy Fax used is ~2+5+3 = 10~.

Sample Input 2

5
1 2 3 5
2 2 1 8
-2 -3 2 4
4 -4 2 7
7 -4 1 2

Sample Output 2

19