Робот должен выполнить \(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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
1 3
3 1
|
2
3 1 2
|