| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 7 | 3 | 1 | 25.000% |
Робот должен выполнить $n$ заданий.
Робот начинает работать в первый день и каждый день может выполнить ровно одну работу. Про каждую работу известен последний день, когда ее можно выполнить и $d_i,ドル и штраф $w_i,ドル который придется заплатить, если работа не будет выполнена в срок.
Помогите роботу решить, в каком порядке выполнять работы, чтобы суммарный штраф был как можно меньше.
Например, если есть 3 работы, первую необходимо выполнить в первый день и штраф за невыполнение 2, вторую также необходимо выполнить в первый день и штраф за невыполнение 3, а третью необходимо выполнить не позже третьего дня и штраф за невыполнение 1, то оптимально выполнить сначала вторую, потом третью, а затем первую работу. В этом случае не в срок выполнено только первая работа и штраф составляет 2. Выполнить одновременно первую и вторую работу в срок невозможно.
В первой строке дано единственное натуральное число $n$ (1ドル \le n \le 200,000円$) --- количество работ.
Затем следует $n$ строк, в каждой из которых содержится по два числа $d_i$ и $w_i$ (1ドル \le d_i \le 200,000円,ドル 1ドル \le w_i \le 200,000円$) --- последний день, когда можно выполнить работу без штрафа и стоимость опоздания для $i$-й работы.
В первой строке выведите единственное число, равное минимальной возможному суммарному штрафу. Во второй строке через пробел выведите $n$ чисел, где $i$-е число --- день, в который необходимо выполнить $i$-ю работу.
Если возможно несколько оптимальных расписаний, выведите любое из них.
3 1 2 1 3 3 1
2 3 1 2
В приведенном робот выполняет в срок вторую и третью работы, а первую выполняет лишь во второй день. Поэтому ему приходится уплатить штраф величиной 2.