시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB70423462.963%

문제

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 number of balls of that size sold and s (1 ≤ s ≤ 10000) the radius of a ball in centimeters.

출력

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

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > The UK & Ireland Programming Contest > UKIEPC 2018 H번

  • 문제의 오타를 찾은 사람: lobo_prix
  • 문제를 만든 사람: Jim Grimmett