Hamster Ball

Interview

Time limit1sMemory limit512 MB

Summary

Tape can seal a ball only if its tape needed is at most the radius; each ball of radius s costs 2*pi*s, so pick sizes with the cheapest cost per ball.

Level: Easy3 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

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?

Input

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.

Output

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.

Examples2

Example 1
Input
```
1000
2
2 30
3 20
```
Expected output
```
5
```
Example 2
Input
```
2000
4
20 30
1 20
1 15
20 25
```
Expected output
```
13
```