Problem
매니저로 일하면서 다음 달 업무 계획을 세웁니다. 각 월은 T 동일한 시간 단위로 나뉩니다. 수행해야 할 작업은 총 n개입니다. 그러나 한 달 안에 모든 작업을 완료하는 것이 불가능할 수 있음을 이해하고 완료할 작업 중 일부를 선택하여 최적의 계획을 세우고 싶습니다.
각 작업에 대해 우리는 그것을 완료하는 데 소요되는 시간 ti와 이익 pi<를 알고 있습니다. /sub> 완료된 작업이 회사에 가져올 것입니다. 다음과 같이 몇 가지 작업을 계획하려고 합니다.
- 계획에 포함된 작업에 소요된 총 시간은
T를 초과하지 않았습니다.
- 이러한 작업의 총 수익은 최대였습니다.
위에서 설명한 속성을 가진 계획을 만들고 이 계획의 구현으로 인한 이익을 결정합니다.
조건과 일치하는 유일한 계획에는 작업이 포함되지 않을 수 있습니다.
데이터 입력
첫 번째 줄에는 자연수 T(1 ≤ T ≤ 100 000) 및 n (1 ≤ n &le ; 10) - 월별 시간 단위 수 및 작업 수
다음 n 행에는 각각 ti 및 pi 두 개의 자연수가 포함됩니다. < /code> (1 <= ti, pi <= 100 000) - 소요 시간 i과제를 완료하고 이를 완료하여 얻을 수 있는 수익
출판 데이터
단일 번호 인쇄 — 위에 적힌 조건을 만족하는 계획을 세워서 얻을 수 있는 최대 수익
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 1 |
10 3
8100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |