Boris

In Philip’s hometown, you can often find the world’s most beautiful billboard. This billboard features none other than the math teacher Boris, along with the text “Count on Boris”. Naturally, Philip has become completely obsessed with collecting these beautiful billboards, and now he needs your help to optimize his route between train stations in the city to collect as many Borises as possible.

Through his extensive network, Philip has learned that in the near future, $N$ trains will depart from the city. For each train, he knows the departure time in seconds after the start of his pursuit, the number of Borises that will be on the train, and the coordinates of the train station, given in meters. To collect the Borises on a train, he must be at the station exactly at the time the train departs, but he can also arrive early and wait for the train calmly if he wishes. Since Philip loves Boris so much and does not want to get stuck on a train that will take him away from his hometown, he is extremely quick at picking up all the Borises on the train and does it in 0 seconds. Note that no matter how early he arrives, he cannot collect the Borises before the train’s departure time, as it is only then that the train doors open.

In such stressful situations as chasing Borises, it becomes very taxing for Philip to keep track of directions accurately. To avoid getting lost, he prefers to move only directly north, south, east, or west, so he knows more easily where he is headed.

Since Philip has plenty of time to prepare for his adventure, he can start anywhere in the city. Once he starts, he moves at a speed of 1 meter/second. Philip has a very large backpack, so he can carry as many Borises as he wants at once.

What is the maximum number of Borises that Philip can collect?

Input

The first line contains an integer $N$ ($1 \le N \le 2,000$), the number of trains.

Following this are $N$ lines, each describing one train. Each line contains four integers: the departure time $t$ in seconds after the start ($0 \le t \le 5 \cdot 10^8$), the number of Borises $s$ on the train ($1 \le s \le 500,000$), and the coordinates $x, y$ of the station from which the train departs ($0 \le x, y \le 5 \cdot 10^8$).

No two trains will depart at the same time from exactly the same station.

Output

Output a single line with an integer – the maximum number of Borises that Philip can collect.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample Case 3

In the third example case, there are four departures. We refer to these as trains $0$ - train $3$, in the order they appear in the input.

If Philip starts at the point $(493,377)$, he can collect $952$ Borises from train $3$ at time $148$. He then has exactly $164$ meters to walk (which takes $164$ seconds) to reach train $1$. This train departs at $312$, which is $164$ seconds after train $3$. So he arrives exactly in time for train $1$ and can collect its $911$ Borises. From there, he has $6$ seconds to walk to train $2$ and collect $927$ Borises. In total, he can collect $952 + 911 + 927 = 2790$ Borises.

2
10 1 0 0
10 1 1 1

1

2
10 1 0 0
12 1 1 1

2

4
332 357 378 891
312 911 650 384
431 927 758 379
148 952 493 377

2790