60014 상자 보관 Platinum IV

문제

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

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

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

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

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

번호	크기	보관 용량
$1$	$6$	$4$
$2$	$5$	$1$
$3$	$9$	$8$
$4$	$2$	$1$

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

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

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

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

입력

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

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

출력

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

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

제한

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

서브태스크

번호	배점	제한
1	7	$N ≤ 6$.
2	12	$s_i = c_i + 1$.
3	26	$N ≤ 1000$.
4	17	$s_i ≤ 100$.
5	38	추가 제약 조건 없음.

4
6 4
5 1
9 8
2 1

1
2
2
2

6
3 2
5 4
3 2
4 3
4 3
3 2

1
1
2
2
2
3

8
13 6
7 5
9 4
11 10
4 2
15 5
16 7
8 3

1
2
3
3
3
4
4
5