G. Время читать книги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для подготовки к ЕГЭ по литературе Арине нужно прочитать n книг за m дней. Для каждой книги она знает di — день, в который нужно завершить чтение i-й книги. Для полноты информации она нагуглила ещё и время ti, которое требуется для прочтения каждой книги.

Далее она определила в каком порядке будет читать книги. Кроме того, Арина решила, что будет читать всю книгу в один день и не переносить чтение на другой день. Теперь она хочет распределить чтение книг так, чтобы наибольшее время, которое ей придётся потратить на чтение книг в день, было наименьшим. Помогите Арине составить план подготовки к экзамену и вывести для каждого дня номер книги, которую она должна будет прочитать в этот день последней. Если в какой-то день Арина может не читать ничего, то выведите в этот день 0.

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

В первой строке содержатся два целых числа n и m (1 ≤ n,  m ≤ 3·105) — количество книг в списке Арины и количество дней, за которые их нужно прочитать.

В каждой из следующих n строк содержится по два целых числа ti и di (1 ≤ ti ≤ 105,  1 ≤ di ≤ m) — время, которое требуется для прочтения книги #i, и день, не позже которого нужно прочитать эту книгу.

Гарантируется, что для всех i верно, что di ≤ di + 1.

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

В первой строке выведите целое число — минимально возможное максимальное время, которое придётся потратить Арине в день для чтения книг из списка.

В каждой из следующих m строк выведите номер книги, которую Арина прочитает в этот день последней, или 0, если в этот день можно ничего не читать.

Пример
Входные данные
4 3
2 2
1 2
2 3
1 3
Выходные данные
3
0
2
4
Примечание

Если Арина будет тратить на чтение книг каждый день не более трёх единиц времени, то в первый день она может не читать ни одной книги. Во второй день может прочитать 1-ю и 2-ю книгу за три единицы времени, и в третий день 3-ю и 4-ю книги.

Правильным ответом будут и другие комбинации, например:(1, 2, 4) или (2, 3, 4) или (2, 0, 4).