Fishing

Interview

Time limit1sMemory limit512 MB

Summary

Each fish is an interval moving horizontally at its own speed; pick one time and one position to stab so that the maximum number of moving intervals contain that point.

Level: Medium7 of 10
Topics: Geometry, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

Donghyun is drifting on the sea. All he has left is a single harpoon. Now that he has grown hungry, he wants to catch fish with the harpoon. Donghyun throws the harpoon straight down, as in the figure below.

$N$ fish live in the sea. For convenience, the current position of the $i$ -th fish is written as the interval [ $S_i$ , $E_i$ ].

However, the fish are alive and keep moving. The speed of the $i$ -th fish is $V_i$ , and it always moves horizontally at a constant speed. So after $t$ seconds, the position of the $i$ -th fish is the interval [ $S_i + tV_i$ , $E_i + tV_i$ ].

Donghyun can throw the harpoon to any position he wants at any time $t \ge 0$ .

If the position where the harpoon is thrown lies inside a fish's interval, he catches that fish. That is, suppose he throws the harpoon to position $x$ after $t$ seconds. If $S_i + tV_i \le x \le E_i + tV_i$ , he has caught the $i$ -th fish.

The harpoon travels so fast that its speed can be ignored. Given that he can throw the harpoon only once, find the maximum number of fish he can catch.

Input

The first line gives the number of fish $N$ . ( $1 \le N \le 1,000$ )

Each of the next $N$ lines gives three integers $S_i$ , $E_i$ , $V_i$ . ( $-1,000,000 \le S_i, E_i, V_i \le 1,000,000$ , $S_i < E_i$ )

Output

Print the maximum number of fish that can be caught.

Examples2

Example 1
Input
```
3
2 3 1
0 1 2
-2 -1 3
```
Expected output
```
3
```
Example 2
Input
```
3
0 1 0
1 2 0
2 3 1
```
Expected output
```
2
```