꺾이지 않는 마음 1

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

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

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

용들은 마법 화살에 잘리더라도 마음이 꺾이지 않는다. $i$번 용의 키가 0이 되었더라도, 다음 날이 되면 키는 다시 $D[i]$만큼 자란다.

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

첫 번째 줄에 용의 수 $N$이 주어진다. ($1 \le N \le 10{,}000$)

이후 $N$개의 줄에 걸쳐 각 용의 정보가 두 정수 $D[i]$, $H[i]$로 주어진다. ($0 \le D[i] \le 10^6$, $0 \le H[i] \le 10^{12}$)

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