고객을 만족시켜라

SG Corp.는 수천 명의 고객을 둔 대형 철강 회사입니다. 모든 고객을 만족시키는 것은 경영진인 Paul과 Art의 최우선 목표입니다.

각 고객은 두 정수로 표현되는 주문을 넣습니다. $q$는 필요한 철강의 양(톤)이고, $d$는 납기(달력상의 날짜를 초로 환산한 값)입니다. SG Corp.가 주문을 수락하면 해당 철강을 납기 이전에 반드시 완성해야 합니다. 공장은 한 번에 최대 하나의 주문만 처리할 수 있습니다.

생산 라인의 처리량은 일정합니다. 철강 $q$톤을 생산하는 데에는 정확히 $q$초가 걸립니다. 공장은 월간 생산 계획으로 운영됩니다. 매달이 시작되기 전에 모든 주문을 모아 Paul과 Art가 어떤 주문을 수락하고 어떤 주문을 거절할지 정한 뒤, 수락한 주문들의 일정을 세웁니다. 고객을 만족시키기 위해 두 사람은 거절하는 주문의 수를 최소화하려 하며, 이는 곧 수락하는 주문의 수를 최대화하는 것과 같습니다. 계획의 시작(그 달의 첫날)을 시각 $0$으로 둡니다.

여러분의 과제는 수락할 수 있는 주문의 최대 개수를 구하는 것입니다.

예로 든 풀이. 다음 6개의 주문 $J_1, \dots, J_6$을 생각해 봅시다. $q_j$는 필요한 철강의 양, $d_j$는 납기입니다.

모든 주문을 수락할 수는 없으며, 최소 두 개는 거절해야 합니다. 한 가지 최적해는 $J_1$과 $J_4$를 거절하고 나머지 네 개를 수락하여 빈틈없이 이어서 처리하는 것입니다.

생산 라인은 한순간도 멈추지 않고, 수락한 모든 주문이 납기 안에 끝나므로 수락된 주문은 4개입니다.

첫째 줄에 주문의 개수 $n$이 주어집니다 ($1 \le n \le 800000$).

이어지는 $n$개의 줄에는 각 주문이 두 정수로 주어집니다. 필요한 철강의 양 $q$ ($1 \le q < 1000$)와 납기 $d$ ($1 \le d < 2 \times 10^6$)이며, 단위는 위와 같습니다.

수락할 수 있는 주문의 최대 개수를 정수 하나로 출력합니다.

• 최적 일정에서는 수락한 주문들을 언제나 납기의 오름차순으로 배열할 수 있습니다.
• 어떤 두 주문 $J_u$, $J_v$에 대해 $q_u > q_v$이고 $d_u < d_v$일 때, $J_u$가 수락되면 $J_v$도 수락되는 최적해가 존재합니다.
• 주문을 납기가 작은 순서대로 처리하면서, 현재 수락한 주문들의 처리 시간 합을 계속 유지하세요. 어떤 주문을 추가했을 때 이 합이 그 주문의 납기를 넘으면, 수락한 주문 중 처리 시간이 가장 큰 것을 제거합니다. 남아 있는 주문의 개수가 정답입니다.