Vazifalar va muddatlar

Sizda $n$ ta vazifa bor, $i$-vazifa $a_i$ vaqt davom etadi va uning muddati $d_i$. Vazifalarni $0$ vaqtdan boshlab ketma-ket, tanaffussiz bajarasiz. Vazifani $f$ vaqtda tugatsangiz, $d_i - f$ ball olasiz (manfiy bo'lishi mumkin). Jami eng ko'p ball qancha bo'ladi?

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Keyingi $n$ ta qatorda $a_i$ va $d_i$ ($1 \le a_i, d_i \le 10^6$).

Bitta son — eng ko'p jami ball.

Ball yig'indisi $\sum d_i - \sum f_i$. Birinchi qism tartibga bog'liq emas, demak tugash vaqtlari yig'indisini kamaytirish kerak: vazifalarni davomiyligi bo'yicha o'sish tartibida bajaring. Qisqa vazifa uzunidan keyin tursa, ularni almashtirish yig'indini kamaytiradi. Muddatlar javobga ta'sir qiladi, lekin tartibga emas.

Ikkinchi misolda tartib $2, 3, 4, 4$, javob $5 + 0 - 7 - 8 = -10$. Javob $-2 \cdot 10^{16}$ gacha yetadi — 64 bitli tur kerak.

Manba: CSES, 1630-masala.