금광에서 일할 수 있는 날이 앞으로 \(N\)일 남았다. 각 날짜에는 그날부터 시작할 수 있는 채굴 작업이 하나씩 있다.

\(i\)번째 날의 채굴 작업을 시작하면 작업을 마치는 데 \(T_i\)일이 걸리고, 작업을 완료했을 때 \(P_i\)만큼의 금을 얻는다. 작업을 진행하는 동안에는 다른 채굴 작업을 시작할 수 없다. 또한 작업은 제시된 날짜에만 시작할 수 있으며, 그날 시작하지 않은 작업은 나중에 시작할 수 없다.

\(N\)일을 넘겨서 끝나는 작업은 시작할 수 없다. 채굴 작업을 적절히 선택하여 얻을 수 있는 금의 최대량을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 금광에서 일할 수 있는 날의 수 \(N\)이 주어진다.

둘째 줄부터 \(N\)개의 줄에 걸쳐 \(i\)번째 날에 시작할 수 있는 작업의 기간 \(T_i\)와 얻을 수 있는 금의 양 \(P_i\)가 공백으로 구분되어 주어진다.

출력

얻을 수 있는 금의 최대량을 출력한다.

제한 사항

• \(1 \le N \le 200,000\)
• \(1 \le T_i \le 50\)
• \(1 \le P_i \le 1,000\)

예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

45

예제 설명 1

첫째 날의 작업과 넷째 날의 작업, 다섯째 날의 작업을 차례대로 진행하면 \(10+20+15=45\)만큼의 금을 얻을 수 있다.