Змагання#8583

Змагання

2 секунди

128 мегабайтів

Середня

У змаганні беруть участь $k$ осіб. Кожен з них повинен пробігти $n$ повних кіл. Усі учасники стартують одночасно зі стартової лінії. На початку кожен бігун знаходиться у своїй "нормальній" формі. Під час бігу витривалість знижується, і кожне наступне коло займає на $1$ мілісекунду більше, ніж попереднє. У нормальній формі учасник з номером $i$ пробігає одне коло за $m s_{i}$ ms_i мілісекунд ( $m s_{i}$ ms_i - додатне ціле число). Правила змагань дозволяють визначити додатне ціле число $p_{i}$ p_i ( $1 \leq p_{i} \leq n$ 1 \le p_i \le n), яке має бути оголошене для кожного учасника перед стартом. Після пробігу $p_{i}$ p_i кіл бігун отримує енергетичний напій (при проходженні стартової лінії), який повертає його в повну силу (після цього витривалість знову знижується так само, як і раніше). Випивка займає $0$ часу. Під час виконання $n$ кіл кожен учасник перетинає стартову лінію $n$ разів (враховується перетин після останнього кола, але не враховується перетин лінії при старті).

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

Вхідні дані

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

Далі йдуть $k$ строк (по одній для кожного бігуна). Кожна строка містить два натуральних числа: $m s_{i}$ ms_i ( $1 \leq m s_{i} \leq 1 0^{6}$ 1 \le ms_i \le 10^6) - кількість мілісекунд, за які бігун номер $i$ пробігає коло в "нормальній" формі, і $p_{i}$ p_i ( $1 \leq p_{i} \leq n$ 1 \le p_i \le n) - кількість кіл, після яких бігун отримує енергетичний напій і повертається в "нормальний" стан.

Вихідні дані

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

Приклади

Приклад 1

Примітка

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

Бігун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 будуть на одній лінії.