В подарочной мастерской упаковывают подарок по принципу матрёшки: коробку вкладывают в коробку побольше, ту — в следующую, и так далее. Мастер перебирает имеющиеся коробки от самой маленькой к самой большой. {2}
Входные данные представлены в файле {1} следующим образом. Первая строка входного файла содержит два числа: — наименьшая допустимая разность размеров соседних коробок и — количество коробок. В каждой из следующих строк записаны два числа: длина ребра очередной коробки в миллиметрах и вид материала, обозначенный числом 0 или 1. Гарантируется, что все длины рёбер различны. Коробки просматривают в порядке возрастания длины ребра. Первая просмотренная коробка образует цепочку, а каждая следующая добавляется в цепочку, если она вмещает последнюю добавленную коробку по правилу из условия; каждая коробка используется не более одного раза.
Пример входного файла:
3 6
10 0
14 1
21 0
22 1
40 0
45 1
{3}