На олимпиаду по информатике прибыло n команд, каждая из которых состоит из ai мальчиков и bi девочек. Для проживания имеются одинаковые комнаты по m мест в каждой. Какое наименьшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?
Первая строка содержит числа n и m. Каждая следующая из n строк содержит пару чисел ai,bi (1≤i≤n). Все числовые значения целые неотрицательные и не превышают 100.
Выведите наименьшее необходимое количество комнат.