컵라면
면접 대비시간 제한2초메모리 제한256 MB
각 문제가 1시간 걸리고 마감 시한과 라면 개수가 주어질 때, 마감을 지키며 풀 문제를 선택해 받을 수 있는 라면의 최대 개수를 구합니다.
문제
상욱 조교는 동호에게 N개의 문제를 주고, 각 문제를 풀면 받을 컵라면 수를 정했다. 동호의 자신감이 너무 커 보이자, 상욱 조교는 각 문제마다 마감일도 함께 정했다.
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4번 문제 순서로 푼다면, 마감일 안에 끝낸 문제는 2, 6, 3, 7번 문제이다. 이때 받을 수 있는 컵라면은 모두 15개이다.
동호가 받을 수 있는 컵라면 수의 최댓값을 구하라. 위의 경우 최댓값은 15이다.
각 문제를 푸는 데에는 단위 시간 1이 걸린다. 각 문제의 마감일은 N 이하의 자연수이다. 또한 각 문제를 풀 때 받을 수 있는 컵라면 수와 동호가 받을 수 있는 컵라면 수의 최댓값은 모두 2^31보다 작은 자연수이다.
입력
첫 줄에 문제의 개수 N (1 ≤ N ≤ 200,000)이 주어진다.
다음 N개의 줄에는 i번째 문제의 마감일과 그 문제를 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 주어진다.
출력
동호가 받을 수 있는 컵라면 수의 최댓값을 출력한다.