시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

The years have been good to the Rock and Roll Hamster Ball company. Starting with a single hamster ball they now produce a popular range of different sizes for hamsters big and small.

Recently they moved manufacturing to a new plant but disaster has happened: The new balls, many of which have been shipped to customers, have a defect. The two halves of the ball do not lock together properly and hamsters are escaping.

The immediate solution is simple. We will send out special hamster ball tape to each customer, they put the hamster in the ball and tape it shut. Problem solved.

Unfortunately you only have a certain amount of tape and you’re not sure it will seal all of the balls that have been shipped. Given the length of tape, the number and radius of hamster balls, what is the largest number of balls you can tape shut?

입력

  • one line containing the integer t (1 ≤ t ≤ 10000), the length of the tape in centimetres.
  • one line containing the integer b (1 ≤ b ≤ 100), the number of different sizes of balls.
  • b lines each with integers d (1 ≤ d ≤ 100), the radius of a ball in centimeters and s (1 ≤ s ≤ 10000) the number of balls of that size sold.

출력

A single line with the integer number of the largest number of balls you can tape shut. If you cannot tape shut any balls, output 0.

예제 입력 1

1000
2
2 30
3 20

예제 출력 1

5

예제 입력 2

2000
4
20 30
1 20
1 15
20 25

예제 출력 2

13