문제
서연이는 동네에서 가장 인기 많은 춤 연습실을 운영하고 있다. N일 간 연습실을 운영 후 N+1일부터 번 돈으로 여행을 가려고 한다.
연습실은 예약을 해야만 사용할 수 있고 연습 시작일을 기준으로 하루에 한 팀의 신청만 받고 있다.
인기가 많은 서연이네 춤 연습실은 하루도 빠짐없이 한 팀 씩 예약 신청이 접수되어 있다.
각각의 신청은 춤 연습을 완료하는데 걸리는 기간 Ti와 연습실을 빌려줬을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 연습실 신청 현황을 보자.
| 1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 |
Ti | 2 | 5 | 1 | 3 | 1 | 3 | 2 |
Pi | 10 | 20 | 8 | 20 | 15 | 40 | 100 |
1일에 신청한 팀은 연습에 총 2일이 소요되며, 연습실을 대여해줬을 때 받을 수 있는 금액은 10이다.
5일에 신청한 팀은 연습에 총 1일이 걸리며, 받을 수 있는 금액은 15이다.
춤 연습을 완료하는데 걸리는 기간이 1일보다 클 수 있기 때문에, 모든 신청을 수락 할 수는 없다.
예를 들어서 1일차 신청을 수락 하게 되면, 2일에 있는 신청은 수락 할 수 없게 된다.
2일에 있는 신청을 수락하게 되면, 3, 4, 5, 6일에 잡혀있는 신청은 수락 할 수 없다.
또한, N+1일째부터는 여행을 떠나기 때문에 6, 7일에 있는 신청은 수락 할 수 없다.
N일간 연습실을 운영할 때 최대 이익은 1일, 3일, 4일에 있는 신청을 수락 하는 것이며, 이때의 이익은 10+8+20=38이다.
최대의 이익을 얻을 수 있도록 연습실 대여 신청을 수락해 주었을 때의 최대 이익을 출력하라.
입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 서연이가 얻을 수 있는 최대 이익을 출력한다.
예제
7
2 10
5 20
1 8
3 20
1 15
3 40
2 100
38
로그인해야 코드를 작성할 수 있어요.