Вазифалар ва муддатлар

Сизда $n$ та вазифа бор, $i$-вазифа $a_i$ вақт давом этади ва унинг муддати $d_i$. Вазифаларни $0$ вақтдан бошлаб кетма-кет, танаффуссиз бажарасиз. Вазифани $f$ вақтда тугатсангиз, $d_i - f$ балл оласиз (манфий бўлиши мумкин). Жами энг кўп балл қанча бўлади?

Биринчи қаторда $n$ ($1 \le n \le 2 \cdot 10^5$). Кейинги $n$ та қаторда $a_i$ ва $d_i$ ($1 \le a_i, d_i \le 10^6$).

Битта сон — энг кўп жами балл.

Балл йиғиндиси $\sum d_i - \sum f_i$. Биринчи қисм тартибга боғлиқ эмас, демак тугаш вақтлари йиғиндисини камайтириш керак: вазифаларни давомийлиги бўйича ўсиш тартибида бажаринг. Қисқа вазифа узунидан кейин турса, уларни алмаштириш йиғиндини камайтиради. Муддатлар жавобга таъсир қилади, лекин тартибга эмас.

Иккинчи мисолда тартиб $2, 3, 4, 4$, жавоб $5 + 0 - 7 - 8 = -10$. Жавоб $-2 \cdot 10^{16}$ гача етади — 64 битли тур керак.

Манба: CSES, 1630-масала.