An Unbroken Heart 1

"N = 10000 is fine. What matters is a heart that does not break"

Your farm has $N$ dragons growing on it. Each dragon has a distinct number from $1$ to $N$. Call today day 1. On day 1, the height of dragon $i$ is $H[i]$. Every time the day changes, the height of every dragon increases by $D[i]$.

Outside the farm, a thief is trying to steal your dragons with a sharp magic arrow. The thief can shoot at most one magic arrow per day, and a shot arrow hits exactly the dragon the thief aims for. When the arrow hits dragon $i$, its height becomes 0, and the thief gets a piece of the dragon equal to the cut length (that is, the height the dragon had before it was hit). The thief may choose not to shoot, and may hit a dragon that was already hit earlier.

The dragons may be cut by the magic arrows, but their hearts do not break. Even if dragon $i$ has height 0, its height increases by $D[i]$ again when the next day comes.

For every $1 \le k \le N$, assume the thief can shoot at most one arrow per day from day 1 to day $k$. Find the maximum possible total length of dragon pieces the thief can obtain.

The first line contains the number of dragons $N$. ($1 \le N \le 10{,}000$)

The next $N$ lines each contain two integers $D[i]$ and $H[i]$. ($0 \le D[i] \le 10^6$, $0 \le H[i] \le 10^{12}$)

Print $N$ lines. On line $i$, print the answer for $k = i$ as a single integer.