Competition

Time limit3sMemory limit128 MB

Summary

Each runner's lap times grow by 1 ms per lap but reset every p_i laps; find the maximum number of runners who cross the start line at the same millisecond.

Level: Medium6 of 10
Topics: Math, Hash map, Implementation, Number theory
Solved: No attempts yet

Problem

$K$ competitors take part in a competition. Each of them must finish exactly $N$ full laps of a circular track, and all competitors start together from the starting line.

At the start every competitor is in 'normal' form. While running they lose stamina and slow down: each lap takes exactly 1 millisecond longer than the previous lap. In normal form, competitor $i$ runs one lap in ms_i milliseconds (a positive integer).

Before the competition, a positive integer p_i ( $1 \le p_i \le N$ ) is fixed for each competitor. Every time the competitor completes a multiple of p_i laps, they receive an energy drink while passing the starting line, which restores them to normal form; afterwards their stamina drops again in the same way. Drinking takes 0 time.

Over the $N$ laps each competitor crosses the starting line exactly $N$ times (the crossing after the final lap is counted, but the crossing at the very start is not).

Determine the maximum number of competitors who cross the starting line at the same moment. Here 'at the same moment' means after an equal number of milliseconds from the start of the competition.

Input

The first line contains two positive integers $K$ and $N$ , separated by a space: $K$ is the number of competitors and $N$ is the number of laps.

Each of the next $K$ lines describes one competitor with two positive integers ms_i and p_i: ms_i is the number of milliseconds competitor $i$ needs to run one lap in normal form, and p_i is the number of laps after which the competitor gets an energy drink and returns to normal form.

Output

Print a single integer: the maximum number of competitors who cross the starting line together at some moment.

Constraints

$2 \le K \le 10000$
$1 \le N \le 1000$
$1 \le ms_i \le 1000000$
$1 \le p_i \le N$

Explanation

For instance, in the example below the competitors run their laps as follows: competitor 1 in 26, 27, 26 ms; competitor 2 in 39, 40, 41 ms; competitor 3 in 45, 45, 45 ms; competitor 4 in 56, 57, 56 ms. They therefore cross the starting line (cumulative milliseconds after the start) at: competitor 1 — 26, 53, 79; competitor 2 — 39, 79, 120; competitor 3 — 45, 90, 135; competitor 4 — 56, 113, 169. The only moment when more than one competitor crosses the line together is at 79 ms, when competitors 1 and 2 meet, so the answer is 2.

Examples4

Example 1
Input
```
4 3
26 2
39 3
45 1
56 2
```
Expected output
```
2
```
Example 2
Input
```
5 4
7 1
7 1
7 1
7 1
7 1
```
Expected output
```
5
```
Example 3
Input
```
2 2
1 1
1000000 1
```
Expected output
```
1
```
Example 4
Input
```
2 3
10 1
15 1
```
Expected output
```
2
```