Сапожник

У сапожника $n$ заказов. Выполнение $i$-го заказа занимает $T_i$ дней. Пока работа над заказом не началась, за каждый день задержки платится штраф $S_i$: если работа над $i$-м заказом начинается после $C$ дней (то есть до него $C$ дней ушло на другие заказы), штраф равен $S_i \cdot C$.

Сапожник работает только над одним заказом одновременно и выполняет заказы подряд без перерывов. Найдите порядок с минимальным суммарным штрафом. Если таких порядков несколько, выведите лексикографически наименьшую последовательность номеров заказов.

В первой строке $n$ ($1 \le n \le 10^5$). В следующих $n$ строках $T_i$ и $S_i$ ($1 \le T_i, S_i \le 10^4$). Заказы пронумерованы от $1$ до $n$.

В первой строке минимальный суммарный штраф. Во второй — $n$ чисел: порядок выполнения заказов.

Перестановка двух соседних заказов $i$ и $j$ меняет только их штрафы: если $i$ раньше, лишний штраф $T_i S_j$, если $j$ раньше — $T_j S_i$. Значит, $i$ ставится раньше $j$, если $T_i S_j < T_j S_i$ (exchange argument — метод обмена). Не сравнивайте отношения как дроби — сравнение произведений точное. При равенстве раньше заказ с меньшим номером.

В примере порядок 2 1 3 4, штраф $0 + 4 \cdot 1 + 2 \cdot 4 + 5 \cdot 6 = 42$. Суммарный штраф достигает $5 \cdot 10^{17}$ — нужен 64-битный тип.

Источник: UVa 10026.