Задачи и сроки

У вас $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.