F. The Austin Longhorn Race
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Passionate fans of the Iditarod Trail Sled Dog Race have created their own version here in Austin, the Austin Longhorn Race.

This year's Austin Longhorn Race features competitors hailing from all over Texas. Interestingly, news of treasure at checkpoints along the route have spread. One team, UT Lemons, has obtained top-secret information about where and when the treasure will appear.

There are $$$N$$$ checkpoints at which the treasure will appear. Each treasure will appear at coordinates ($$$X_i$$$, $$$Y_i$$$) and at time $$$T_i$$$ for $$$(1 \leq i \leq N)$$$. Each treasure is worth $$$V_i$$$ gold coins.

Every team starts from $$$(0, 0)$$$ at time = $$$0$$$, and moves at a rate of one unit distance per unit time. UT Lemons will be able to obtain the treasure at checkpoint $$$i$$$ if they are at $$$X_i$$$, $$$Y_i$$$ at time $$$T_i$$$. The total treasure value is the sum of individual treasure values. Please help UT Lemons determine the maximum amount of treasure they can obtain (measured in gold coins).

Input

The first line contains one integer, $$$N$$$ ($$$1 \leq N \leq 5000$$$).

The next $$$N$$$ lines contain four integers, $$$X_i$$$, $$$Y_i$$$, $$$T_i$$$, $$$V_i$$$ ($$$1 \leq i \leq N$$$, $$$0 \leq X_i, Y_i, T_i, V_i \leq 10^9$$$).

Output

A single integer representing the total number of gold coins that UT Lemons can obtain by taking the best route.

Examples
Input
3
1 1 100 10
2 2 40 8
20 20 25 1000
Output
18
Input
2
15 20 25 100
7 24 25 50
Output
100