각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다.

단, 보석은 쪼갤 수 없고 종류당 하나씩 있다고 하자.

입력 방법

• 첫 줄에는 도둑이 가져갈 수 있는 무게를,
• 다음 줄에는 보석의 개수,
• 다음 줄 부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다.

가방의 크기는 10000 이하이고 , 보석의 개수는 100 개 이하 무게와 가격은 200 이하의 정수이다.

출력 방법

입출력 예

입력

30
3
5 50
10 60
20 140

출력

200