퇴사 전 상담 일정

상담원으로 일하는 민준이는 퇴사를 준비한다.

오늘부터 N+1일째 되는 날 퇴사하기 위해, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

민준이는 비서에게 상담을 최대한 많이 잡아 달라고 부탁했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아 두었다.

각 상담은 상담을 완료하는 데 걸리는 기간 $T_i$와 상담을 마쳤을 때 받는 금액 $P_i$로 이루어진다.

N = 7인 경우의 상담 일정표를 보자.

1일에 잡힌 상담은 3일이 걸리고, 상담을 마쳤을 때 받는 금액은 10이다. 5일에 잡힌 상담은 2일이 걸리고, 받는 금액은 15이다.

상담 하나에 필요한 기간이 1일보다 길 수 있어서 모든 상담을 할 수는 없다. 예를 들어 1일에 상담을 시작하면 2일과 3일에 있는 상담은 하지 못한다. 2일에 있는 상담을 시작하면 3일, 4일, 5일, 6일에 잡힌 상담을 하지 못한다.

또한 N+1일째에는 회사에 없으므로 6일과 7일에 있는 상담도 하지 못한다.

퇴사 전에 얻을 수 있는 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이고, 이때의 이익은 10+20+15=45이다.

상담을 적절히 골랐을 때 민준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

첫째 줄에 N ($1 \le N \le 1500000$)이 주어진다.

둘째 줄부터 N개의 줄에 $T_i$와 $P_i$가 공백으로 구분되어 주어지며, 1일부터 N일까지 순서대로 주어진다. ($1 \le T_i \le 50$, $1 \le P_i \le 1000$)

첫째 줄에 민준이가 얻을 수 있는 최대 이익을 출력한다.