상자 보관

정올이는 창고에 상자를 보관하려고 한다. 상자는 총 $N$개가 있으며 $1$부터 $N$까지의 번호가 붙어 있다. $i$ ($1 \le i \le N$)번 상자의 크기는 $s_i$, 보관 용량은 $c_i$이다. 모든 상자는 보관 용량이 그 크기보다 작다. 즉, $c_i < s_i$ 를 만족한다.

창고에 상자가 너무 많아 복잡하다고 생각한 정올이는, 상자를 다른 상자의 안에 넣어서 보관하고자 한다. 이때, 다음과 같은 조건이 만족되어야 한다.

• 한 상자에는 해당 상자의 보관 용량 이하의 크기를 갖는 상자를 넣을 수 있다.
• 이미 상자를 포함한 상자를 다른 상자 안에 넣는 것도 가능하다.
• 한 상자에 직접 포함되는 상자는 최대 하나여야 한다. 다시 말해, 한 상자 안에는 다른 상자를 최대 하나 넣을 수 있지만, 그 다른 상자 안에 또 다른 상자들이 들어가 있는 것은 허용된다.

상자를 보관하는 비용은 다른 상자에 포함되지 않은 상자의 개수와 같다.

예를 들어, $N = 4$이고, 네 상자의 크기와 보관 용량이 각각 아래 표와 같은 경우를 생각하자.

이때, 아래 그림처럼 $4$번 상자를 $1$번 상자에 넣고, $1$번 상자를 $3$번 상자에 넣으면, 다른 상자에 포함되지 않은 상자의 수는 $2$개가 되고, 따라서 상자를 보관하는 비용은 $2$가 된다.

그러나 아래 그림처럼 $2$번 상자와 $4$번 상자를 $3$번 상자에 넣는 경우, $3$번 상자 안에 두 개의 상자가 직접 포함되어 있으므로, 조건을 만족하지 않는다.

창고에 반드시 모든 상자를 둘 필요는 없어서, 정올이는 번호가 작은 몇 개의 상자만 보관하고 나머지 상자는 버릴 계획을 하고 있다. 정올이는 아직 몇 개의 상자를 사용할지는 정하지 못한 상태이다.

정올이를 도와, $1$부터 $N$까지의 모든 $i$에 대해, $1, 2, \ldots, i$번 상자를 보관하는 데 드는 최소 비용을 계산하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 2 \times 10^5$
• $1 \le c_i < s_i \le 10^9$ $(1 \le i \le N)$

1. (7점) $N \le 6$.
2. (12점) $s_i = c_i + 1$.
3. (26점) $N \le 1000$.
4. (17점) $s_i \le 100$.
5. (38점) 추가 제약 조건 없음.

첫 번째 줄에는 상자의 수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 상자의 정보가 주어진다. 이 중 $i$번째 줄에는 $i$번 상자의 크기 $s_i$와 보관 용량 $c_i$가 공백을 사이에 두고 주어진다.

$N$개의 줄을 출력한다.

$i$ ($1 \le i \le N$)번째 줄에는 $1, 2, \ldots, i$번 상자를 보관하는 데 드는 최소 비용을 출력한다.