Персик — акула в мире программирования — решил составить расписание для всех профилей олимпиады Innopolis Open.
В учебном году $$$D$$$ дней, пронумерованных от $$$1$$$ до $$$D$$$. Всего проводится $$$n$$$ олимпиад.
Олимпиады пронумерованы от $$$1$$$ до $$$n$$$ в порядке неубывания запланированной даты проведения. Каждая олимпиада проводится ровно в один день. Для каждой олимпиады известны её запланированная дата проведения и польза для подрастающего поколения.
Вы можете изменить дату проведения каждой олимпиады, но только на более поздний день того же учебного года (то есть новую дату нельзя сделать меньше исходной и нельзя сделать больше $$$D$$$).
После всех изменений олимпиады должны остаться в порядке неубывания даты проведения.
Польза олимпиадного сезона определяется следующим образом. Для каждого дня рассматриваются все олимпиады, проводящиеся в этот день. Если в день запланирована хотя бы одна олимпиада, то польза дня определяется как максимум значений пользы среди олимпиад, проводящихся в этот день. Если в этот день олимпиад нет, польза дня равна $$$0$$$.
Польза сезона равна сумме пользы всех $$$D$$$ дней.
Во благо школьников определите наибольшую возможную пользу сезона.
В первой строке даны три целых числа $$$n$$$, $$$D$$$ и $$$t$$$ — количество олимпиад и количество дней в учебном году, а также тип ответа ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le D \le 2 \cdot 10^9$$$; $$$1 \le t \le 2$$$).
В $$$i$$$-й из следующих $$$n$$$ строк даны два целых числа $$$d_i$$$ и $$$b_i$$$ — запланированная дата (номер дня) проведения и польза $$$i$$$-й олимпиады ($$$1 \le d_i \le D$$$; $$$1 \le b_i \le 2 \cdot 10^9$$$).
Гарантируется, что $$$d_i \le d_j$$$ для всех $$$i$$$ и $$$j$$$, таких что $$$i \lt j$$$.
Если $$$t = 1$$$, то выведите одно целое число — наибольшую возможную пользу олимпиадного сезона.
Если $$$t = 2$$$, то в первой строке выведите одно целое число — наибольшую возможную пользу олимпиадного сезона; а во второй строке выведите расписание олимпиад — $$$n$$$ целых чисел, $$$i$$$-е из которых является итоговой датой $$$i$$$-й олимпиады. При указанных итоговых датах должна достигаться максимально возможная польза олимпиадного сезона.
Тесты к этой задаче состоят из тринадцати групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых для неё групп.
| Группа | Баллы | Доп. ограничения | Необходимые группы |
| 1 | 10 | $$$n, D \le 20$$$; $$$b_i \le 20$$$ для всех $$$i$$$; $$$t = 1$$$ | – |
| 2 | 7 | $$$n, D \le 20$$$; $$$b_i \le 20$$$ для всех $$$i$$$ | 1 |
| 3 | 11 | $$$n, D \le 100$$$; $$$b_i \le 100$$$ для всех $$$i$$$ | 1, 2 |
| 4 | 9 | $$$n, D \le 800$$$; $$$b_i \le 800$$$ для всех $$$i$$$ | 1, 2, 3 |
| 5 | 5 | $$$n, D \le 2500$$$; $$$b_i \le 2500$$$ для всех $$$i$$$; $$$t = 1$$$ | 1 |
| 6 | 4 | $$$n, D \le 2500$$$; $$$b_i \le 2500$$$ для всех $$$i$$$ | 1–5 |
| 7 | 5 | $$$b_i = b_j$$$ для всех $$$i$$$, $$$j$$$ | – |
| 8 | 5 | $$$d_i \neq d_j$$$ для всех $$$i$$$ и $$$j$$$, таких что $$$i \neq j$$$ | – |
| 9 | 5 | $$$d_i = 1$$$ для всех $$$i$$$; $$$t = 1$$$ | – |
| 10 | 5 | $$$d_i = d_j$$$ для всех $$$i$$$, $$$j$$$ | 9 |
| 11 | 8 | $$$D \le 2 \cdot 10^6$$$ | 1–6 |
| 12 | 10 | $$$t = 1$$$ | 1, 5, 9 |
| 13 | 16 | – | 1–12 |
3 10 11 31 51 2
10
3 10 21 31 51 2
10 1 2 3
5 6 21 72 65 85 96 4
30 1 3 5 6 6
Заметьте, что ответ для второго теста не подойдёт в качестве ответа для первого, так как при $$$t = 1$$$ нужно выводить только одно число.
Во втором примере в предлагаемом ответе польза первого дня равна $$$3$$$, польза второго — $$$5$$$, третьего — $$$2$$$, а пользы дней с $$$4$$$-го по $$$10$$$-й равны $$$0$$$. Таким образом, польза олимпиадного сезона равна $$$3+5+2+0+\ldots+0=10$$$. Заметьте, что расписание олимпиад $$$[2, 1, 3]$$$ невозможно, так как олимпиады должны остаться в порядке неубывания даты проведения.
В третьем примере также подходит расписание олимпиад $$$[1, 2, 5, 6, 6]$$$, но не подходит $$$[1, 2, 3, 5, 6]$$$, так как третья олимпиада не может проходить раньше $$$5$$$-го дня.
