서연이는 동네에서 가장 인기 많은 춤 연습실을 운영하고 있다. N일 간 연습실을 운영 후 N+1일부터 번 돈으로 여행을 가려고 한다.

연습실은 예약을 해야만 사용할 수 있고 연습 시작일을 기준으로 하루에 한 팀의 신청만 받고 있다.

인기가 많은 서연이네 춤 연습실은 하루도 빠짐없이 한 팀 씩 예약 신청이 접수되어 있다.

각각의 신청은 춤 연습을 완료하는데 걸리는 기간 Ti와 연습실을 빌려줬을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 연습실 신청 현황을 보자.

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이다.

최대의 이익을 얻을 수 있도록 연습실 대여 신청을 수락해 주었을 때의 최대 이익을 출력하라.

[swat]연습실 timer 2s memory 512MB

[swat]연습실 2s 512MB