Feeding the Panda

Time limit2sMemory limit128 MB

Summary

Find the longest sequence of bamboo groves with strictly increasing tastiness where consecutive Manhattan distance stays within the destination's bamboo count.

Level: Hard8 of 10
Topics: Dynamic programming, Geometry, Segment tree, Sorting
Solved: No attempts yet

Problem

Teddy the panda lives in a forest with N bamboo groves. Each bamboo grove is represented by a point on a plane. The i-th grove has a tastiness value W_i and contains L_i bamboo stalks.

Each day, Teddy chooses one bamboo grove and eats all of its bamboo. From the second day on, he may move only to a grove whose tastiness value is strictly greater than the grove he ate from on the previous day.

The longer Teddy walks, the more bamboo he expects. If the Manhattan distance from the previous grove to the current grove is greater than the current grove's bamboo count L_i, Teddy starts crying. In other words, a move to grove i is allowed only when |x_0 - x_1| + |y_0 - y_1| <= L_i.

You may choose Teddy's starting grove. Find the maximum number of days Teddy can eat bamboo without crying.

Input

The first line contains the number of bamboo groves N.

Each of the next N lines describes one grove with four space-separated integers X_i, Y_i, W_i, and L_i: its coordinates, tastiness value, and bamboo count.

Output

Print the maximum number of days Teddy can eat bamboo without crying.

Constraints

1 <= N <= 100,000
0 <= X_i, Y_i <= 100,000
0 <= W_i <= 50,000
0 <= L_i <= 200,000

Examples1

Example 1
Input
```
3
0 0 3 4
2 2 2 3
5 5 1 3
```
Expected output
```
2
```