정올이는 창고에 상자를 보관하려고 한다. 상자는 총 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,…,i\)번 상자를 보관하는 데 드는 최소 비용을 계산하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• \(2≤N≤2×10^5\)\
• \(1≤c_i

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

두 번째 줄부터 \(N\)개의 줄에 걸쳐 각 상자의 정보가 주어진다.

이 중 \(i\)번째 줄에는 \(i\)번 상자의 크기 \(s_i\) 와 보관 용량 \(c_i\) 가 공백을 사이에 두고 주어진다.

\(N\)개의 줄을 출력한다.

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 초등부 4번