4530 - Robber Robber (Challenge)

Time Limit: 1s Memory Limit: 128MB

Submissions: 49 Solved: 16
Description

로버씨는 불난 집에서 급하게 몇몇 물건만 챙겨서 빠져나가려고 한다.

모든 물건을 전부 가져가고 싶지만 안타깝게도 로버씨가 한 번에 옮길 수 있는 무게에는 한계가 있다.

그리고 집이 무너지기 직전이기 때문에 한번 들고 나가면 다시 들어올 수 없다.

그래서 로버씨는 들 수 있는 무게 안에서 최대한 챙겨서 빠져나가려고 한다.

로버씨가 한 번에 가져갈 수 있는 물건들의 가격 총합은 최대 얼마인지 계산해보자.

Input

Line 1: 로버씨가 한 번에 들 수 있는 최대 무게 W (1 ≤ W ≤ 100)

Line 2: 물건 갯수 N (1 ≤ N ≤ 100)

Line 3~N+2: 물건의 가격 p, 무게 w  (1 ≤ p,w ≤ 100)

Output

Line 1: 로버씨가 챙길 수 있는 최대 가격

Sample Input
15
3
10 13
6 6
5 6
Sample Output
11