꺾이지 않는 마음 3

"N = 10000 × 10 × 10은 괜찮다. 중요한 것은 꺾이지 않는 마음"

당신의 농장에는 N마리의 용이 자라고 있다. 각 용에는 1부터 N까지 서로 다른 번호가 붙어 있다. 오늘을 1일이라고 할 때, 1일의 $i$번 용의 키는 $H_i$이다. 하루가 바뀔 때마다 모든 용의 키가 $D_i$만큼 자란다.

농장 밖에서는 도적이 당신의 용을 탐내어 날카로운 마법 화살로 용을 훔치려고 한다. 도적은 매일 최대 하나의 마법 화살을 쏠 수 있으며, 도적이 쏜 화살은 도적이 원하는 용에 정확히 맞는다. 화살이 $i$번 용에 적중하면 $i$번 용의 키는 0이 되고, 도적은 마법 화살의 힘을 빌려 잘린 길이(즉, 잘리기 전 용의 키)만큼의 용 조각을 얻는다. 도적은 화살을 쏘지 않을 수도 있으며, 한 번 화살을 맞은 용에 나중에 다시 화살을 적중시킬 수도 있다.

당신의 용들은 마법 화살에 잘릴지언정 그 마음은 꺾이지 않는다. $i$번 용의 키가 0이 되었더라도, 다음 날이 되면 키가 다시 $D_i$만큼 자란다.

모든 $1 ≤ k ≤ N$에 대해, 도적이 1일부터 $k$일까지 매일 최대 한 번 화살을 쏠 수 있다고 가정할 때 얻을 수 있는 용 조각 길이 합의 최댓값을 구하여라.

첫 번째 줄에 용의 수 N이 주어진다. ($1 ≤ N ≤ 10^6$)

이후 N개의 줄에 걸쳐 각 용의 정보가 두 정수 $D_i$, $H_i$로 주어진다. ($0 ≤ D_i ≤ 10^6$, $0 ≤ H_i ≤ 10^{12}$)

N개의 줄을 출력하라. $i$번째 줄에는, $k = i$일 때의 답을 하나의 정수로 출력하라.