Velociraptors 201 P46713


Statement
 

pdf   zip

html

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 t≤ T 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++