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

Входные данные

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

Выходные данные

Вывести наименшее необходимое количество комнат.