34207번 - 상자 보관 서브태스크

문제

정올이는 창고에 상자를 보관하려고 한다. 상자는 총 $N$개가 있으며 1ドル$부터 $N$까지의 번호가 붙어 있다. $i$ (1ドル ≤ i ≤ 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, \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$)

서브태스크

힌트