Competition#8583

Competition

2 seconds

128 megabytes

Medium

$k$ competitors are taking part in a competition. Each of them must finish $n$ full laps of a round circuit. All the competitors start together from the starting line. At the start of the event every runner is in his 'normal' form. While making his laps he is losing his stamina and he is running with lower and lower tempo. That lower tempo means that every lap is done $1$ millisecond slower than the previous one. When in normal form competitor with number $i$ is doing one lap for $m s_{i}$ ms_i milliseconds ( $m s_{i}$ ms_i is a positive integer). The rules of the competition allow a positive integer $p_{i}$ p_i ( $1 \leq p_{i} \leq n$ 1 \le p_i \le n) to be announced for every competitor before the start. On every full $p_{i}$ p_i laps done the runner gets an energy drink (while passing the starting line) which returns him to full strength (after that his stamina is dropping again the same way as before). The drinking takes $0$ time. It's obvious that while doing $n$ laps every competitor will cross the starting line $n$ times (we count the crossing after the last lap, but do not count the crossing of the line when they start the run).

Write a program, which determines the maximum number of competitors who will cross the starting line together at any point of the competition (as we are working in milliseconds "together" means after equal amount of milliseconds after the competition's start).

Input

The first line contains two positive integers, separated by a space: $k$ ( $2 \leq k \leq 10000$ 2 \le k \le 10000) - competitors count and $n$ ( $1 \leq n \leq 1000$ 1 \le n \le 1000) - laps count.

After that there are $k$ rows (one for each runner). On every row there are two positive integers: $m s_{i}$ ms_i ( $1 \leq m s_{i} \leq 1 0^{6}$ 1 \le ms_i \le 10^6) - milliseconds for competitor $i$ to run one lap in "normal" form and $p_{i}$ p_i ( $1 \leq p_{i} \leq n$ 1 \le p_i \le n) - lap count on which the runner receives his energy drinks and returns to "normal" form.

Output

Print one single integer - the determined maximum count of competitors who will cross the starting line together at some moment of the competition.

Examples

Example 1

Note

The runners will do the following laps:

Runner1 - for $26$ , $27$ and $26$ msec.; Runner2 - for $39$ , $40$ and $41$ msec.; Runner3 - for $45$ , $45$ and $45$ msec.;Runner4 - for $56$ , $57$ and $56$ msec. Respectively they will cross the starting line at: Runner1 - after $26$ , $53$ , $79$ msec.; Runner2 - after $39$ , $79$ and $120$ msec; Runner3 - after $45$ , $90$ and $135$ msec; Runner4 - after $56$ , $113$ and $169$ msec. The only case when more than one runner will cross the starting line is after $79$ milliseconds whenrunner1 and runner2 will be on the line together.