Informatica Online Judge

  Score Inflation [0290 / 0122]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 23   Total Tried : 29


The Champion of this Problem (C++) : tlsdydaud1 - 82ms / 225byte
My Best Submission (C++) : N/A

[]

Background

USACO대회에 참가하는 우리는 더 많은 점수를 얻으면 더 행복해진다. 우리는 되도록이면 사람들이 더 많은 점수를 얻을 수 있도록 대회를 만들고자 한다.


우리가 설계하는 대회는 N개의 카테고리에 있는 문제를 M분 동안 풀어야 하는데, 각 카테고리에서 적절하게 몇 개의 문제를 선택하여 풀 수 있다.

각 카테고리의 문제들은 풀었을 때 걸리는 시간과 점수가 같다.

각 각 카테고리의 문항 당 우리가 얻을 수 있는 점수와 푸는 데 걸리는 시간이 주어지고, 대회에 풀어야하는 문제의 수와 시간이 주어질 때, 얻을 수 있는 점수를 최대화 할 수 있는 프로그램을 작성하시오.

Input

첫 번째 줄에 시간 M과 카테고리의 수 N이 공백으로 구분되어 입력된다. 이 두 값은 모두 10,000이하의 자연수이다.
두 번째 줄부터 N+1번째 줄까지 각 카테고리별로 각 문제의 점수와 문제를 푸는데 걸리는 시간이 공백으로 구분되어 입력된다.

Output

얻을 수 있는 최대 점수를 출력한다.

IO Example

입력
300 4
100 60
250 120
120 100
35 20

출력
605

* 설명 : 2번 카테고리에서 2문제, 4번 카테고리에서 3문제를 풀면 605점을 받을 수 있고 더 이상 받을 수 있는 방법은 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]