상자 보관 timer 2s memory 1024MB

정올이는 창고에 상자를 보관하려고 한다. 상자는 총 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<s_i≤10^9 (1≤i≤N)