Для подготовки к ЕГЭ по литературе Арине нужно прочитать 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).
| Финал ВКОШП.Junior 2025 |
|---|
| Закончено |
