Competition

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 ms[i] milliseconds (ms[i] is a positive integer). The rules of the competition allow a positive integer p[i] (1 ≤ p[i] ≤ n) to be announced for every competitor before the start. On every full 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

On the first line you must read two positive integers, separated with an interval: k (2 ≤ k ≤ 10000) - competitors count and n (1 ≤ n ≤ 1000) - laps count.

After that there are k rows (one for each runner). On every row there are two positive integers: ms[i] (1 ≤ ms[i] ≤ 10^6) - milliseconds for competitor i to run one lap in "normal" form and p[i] (1 ≤ p[i] ≤ 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

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, 79msec.; Runner2 - after 39, 79 and 120 msec; Runner3 - after 45, 90 and 135 msec; Runner4 - after 56, 113 and169 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.