Соревнование
В соревновании принимает участие 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 будут на одной линии.