Etikdo'z

Etikdo'zda $n$ ta buyurtma bor. $i$-buyurtmani bajarish $T_i$ kun davom etadi. Buyurtma ustida ishlash boshlanmaguncha har bir kechikkan kun uchun $S_i$ so'm jarima to'lanadi: $i$-buyurtma ishi $C$-kun oxirida boshlansa (ya'ni undan oldin $C$ kun boshqa buyurtmalar bilan o'tgan bo'lsa), jarima $S_i \cdot C$.

Etikdo'z bir vaqtda faqat bitta buyurtma ustida ishlaydi va buyurtmalarni uzluksiz, ketma-ket bajaradi. Jami jarima eng kichik bo'ladigan tartibni toping. Bunday tartiblar bir nechta bo'lsa, buyurtma raqamlari ketma-ketligi leksikografik eng kichigini chiqaring.

Birinchi qatorda $n$ ($1 \le n \le 10^5$). Keyingi $n$ ta qatorda $T_i$ va $S_i$ ($1 \le T_i, S_i \le 10^4$). Buyurtmalar $1$ dan $n$ gacha raqamlangan.

Birinchi qatorda eng kichik jami jarima. Ikkinchi qatorda $n$ ta son — buyurtmalarni bajarish tartibi.

Yonma-yon turgan $i$ va $j$ buyurtmalarning o'rnini almashtirish faqat shu ikkisining jarimasini o'zgartiradi: $i$ oldin bo'lsa ortiqcha jarima $T_i S_j$, $j$ oldin bo'lsa $T_j S_i$. Demak $i$ ni $j$ dan oldin qo'yish kerak, agar $T_i S_j < T_j S_i$ bo'lsa (exchange argument). Nisbatlarni kasr ko'rinishida solishtirmang — ko'paytmalarni solishtirish aniq. Teng bo'lsa, raqami kichigi oldin.

Misolda tartib 2 1 3 4, jarima $0 + 4 \cdot 1 + 2 \cdot 4 + 5 \cdot 6 = 42$. Jami jarima $5 \cdot 10^{17}$ gacha yetadi — 64 bitli tur kerak.

Manba: UVa 10026.