# Velociraptors 201 P46713

Statement

thehtml

You are going down in the lift of your home when you observe that the sensor of velociraptor flickers: it means that there is a velociraptor in the hall, waiting that the lift goes down to devour you. Other kind of person would cross his arms and would say that, Oh, well! This kind of things happen sometimes; luckely, you always bring the kit of self-defense against velociraptors that you bought in the home shopping service. When you open it, however, discover that the kit is just a plastic lance, in pieces, which instructions do not worth to follow because the whole lance will not fit in the lift. Ready, however, to defend the image of the human race, you are going to prepare the longest piece of lance that fits in the lift.

Kit is formed by n pieces in the shape of a tube, each one of them has a length li and a diameter di. the hooks of the pieces are such that you only can hook up a narrow tube in a wider one, so that the diameter of the result lance decreases every time you hook up a tube. In particular, you cannot hook up two tubes of the same diameter. You are asked to, given the maximal length T that fits in the lift, and the lengths and diameters of the n pieces, discover which is the lance of greatest lenght t with tT that you can assemble.

Input

A test data contains various cases. Each case is described in various lines. The first one contains two naturals T and n, with 1≤ T ≤ 1000 and 1 ≤ n ≤ 100, that describe the maxinal size of lance that fits in the lift and the number of pieces. Then, n lines come, each one with a pair of numbers di, li separated by spaces, that describe the n lengths and diameters in milimetres of the pieces. It is fulfilled that 1≤ di, li≤ 1000.

Output

Your program must print for each case, the size t of the maximal lance that fits in the lift and you can form using the pieces in the described way.

Scoring

• Test1:  ‍40 Points ‍

Solving a test data that contains 100 situations with n ≤ 15, T ≤ 100, and where the di are different and are given in decreasing order of diameter (as in the instance 1).

• Test2:  ‍60 Points ‍

Solving a test data that contains 100 situations of all kinds.

Public test cases
• Input

100 5
10 1000
9 80
8 30
7 60
5 25

100 1
10 101

100 1
10 100

100 5
90 42
80 37
70 12
60 87
50 18

100 15
15 64
14 23
13 17
12 8
11 83
10 43
9 29
8 57
7 34
6 12
5 15
4 9
3 41
2 63
1 8

Output

90
0
100
99
100

• Input

10 3
1 5
1 5
2 4

10 6
5 1
5 2
5 3
5 4
5 5
3 7

10 5
10 11
7 15
12 2
11 3
13 4

Output

9
10
9

• Input

892 27
4 64
2 1893
2 2350
11 2668
4 2336
13 223
1 916
7 537
8 42
3 131
3 546
1 1862
2 660
2 427
1 962
3 1067
4 393
6 923
11 1166
2 298
12 56
3 328
2 120
3 735
2 1642
6 415
3 274

Output

891

• Information
Author
Omer Giménez
Language
English
Translator
Carlos Molina
Original language
Spanish
Other languages
Spanish
Official solutions
C++
User solutions
C++