퇴사

상담원으로 일하는 준호는 퇴사를 하려고 한다.

오늘부터 $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 15$)이 주어진다.

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

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