Shoemaker

A shoemaker has $n$ orders. Order $i$ takes $T_i$ days. Until work on an order starts, a fine of $S_i$ is paid for every day of delay: if work on order $i$ starts after $C$ days (that is, $C$ days were spent on other orders before it), the fine is $S_i \cdot C$.

The shoemaker works on one order at a time and does the orders one after another without breaks. Find an order of jobs with the minimum total fine. If there are several, print the lexicographically smallest sequence of order numbers.

The first line contains $n$ ($1 \le n \le 10^5$). The next $n$ lines contain $T_i$ and $S_i$ ($1 \le T_i, S_i \le 10^4$). Orders are numbered from $1$ to $n$.

The first line contains the minimum total fine. The second line contains $n$ numbers — the order of the jobs.

Swapping two neighbouring orders $i$ and $j$ changes only their fines: with $i$ first the extra fine is $T_i S_j$, with $j$ first it is $T_j S_i$. So $i$ goes before $j$ if $T_i S_j < T_j S_i$ (an exchange argument). Do not compare the ratios as fractions — comparing the products is exact. On a tie the smaller number goes first.

In the example the order is 2 1 3 4 with fine $0 + 4 \cdot 1 + 2 \cdot 4 + 5 \cdot 6 = 42$. The total fine reaches $5 \cdot 10^{17}$ — a 64-bit type is needed.

Source: UVa 10026.