27276번 - Робот 스페셜 저지다국어

Робот должен выполнить $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$-ю работу.

Если возможно несколько оптимальных расписаний, выведите любое из них.

В приведенном робот выполняет в срок вторую и третью работы, а первую выполняет лишь во второй день. Поэтому ему приходится уплатить штраф величиной 2.