Змагання

У змаганні беруть участь k осіб. Кожен з них повинен пробігти n повних кіл. Усі учасники стартують одночасно зі стартової лінії. На початку кожен бігун знаходиться у своїй "нормальній" формі. Під час бігу витривалість знижується, і кожне наступне коло займає на 1 мілісекунду більше, ніж попереднє. У нормальній формі учасник з номером i пробігає одне коло за ms[i] мілісекунд (ms[i] - додатне ціле число). Правила змагань дозволяють визначити додатне ціле число p[i] (1 ≤ p[i] ≤ n), яке має бути оголошене для кожного учасника перед стартом. Після пробігу p[i] кіл бігун отримує енергетичний напій (при проходженні стартової лінії), який повертає його в повну силу (після цього витривалість знову знижується так само, як і раніше). Випивка займає 0 часу. Під час виконання n кіл кожен учасник перетинає стартову лінію n разів (враховується перетин після останнього кола, але не враховується перетин лінії при старті).

Напишіть програму, яка визначить максимальну кількість учасників, які будуть перетинати стартову лінію одночасно в будь-який момент змагань (оскільки ми працюємо в мілісекундах, "одночасно" означає в той самий момент часу після початку змагання).

Вхідні дані

Перша строка містить два натуральних числа: кількість учасників k (2 ≤ k ≤ 10000) і кількість кіл n (1 ≤ n ≤ 1000).

Далі йдуть k строк (по одній для кожного бігуна). Кожна строка містить два натуральних числа: ms[i] (1 ≤ ms[i] ≤ 10^6) - кількість мілісекунд, за які бігун номер i пробігає коло в "нормальній" формі, і p[i] (1 ≤ p[i] ≤ n) - кількість кіл, після яких бігун отримує енергетичний напій і повертається в "нормальний" стан.

Вихідні дані

Виведіть одне ціле число - максимальну кількість учасників, які в якийсь момент змагання будуть одночасно перетинати стартову лінію.

Приклади

Примітка

Бігуни пройдуть кола наступним чином:

Бігун1 - за 26, 27 і 26 мсек.; Бігун2 - за 39, 40 і 41 мсек.; Бігун3 - за 45, 45 і 45 мсек.; Бігун4 - за 56, 57 і 56 мсек. Відповідно, вони перетнуть стартову лінію в: Бігун1 - після 26, 53, 79 мсек.; Бігун2 - після 39, 79 і 120 мсек.; Бігун3 - після 45, 90 і 135 мсек.; Бігун4 - після 56, 113 і 169 мсек. Єдиний випадок, коли стартову лінію перетне одночасно більше одного учасника, - це після 79 мілісекунди, коли Бігун1 і Бігун2 будуть на одній лінії.