Velocirráptors 201 P46713


Statement
 

pdf   zip

thehtml

Estás bajando en el ascensor de tu casa cuando observas que el detector de velocirráptors parpadea: eso quiere decir que hay un velocirráptor en el vestíbulo, esperando que el ascensor baje para devorarte. Otro tipo de persona cruzaría los brazos y diría que, en fin, estas cosas pasan; por suerte, siempre tienes a mano el kit de defensa personal anti-velocirráptors de la tele-tienda. Cuando lo abres, sin embargo, descubres que el kit no es más que una lanza de plástico, a piezas, cuyas instrucciones de montaje no vale la pena seguir puesto que la lanza entera no cabrá en el ascensor. Dispuesto, sin embargo, a dejar en buen papel a la raza humana, te dispones a montar el trozo de lanza más largo que te quepa dentro del ascensor.

El kit está formado por n piezas con forma de tubo, cada una de las cuales tiene una longitud li y un diámetro di. Los enganches de las piezas son tales que sólo puedes enganchar un tubo estrecho en uno más ancho, y de tal modo que el diámetro de la lanza resultante vaya siempre decreciendo a medida que vas enganchando tubos. En particular, no puedes enganchar dos tubos del mismo diámetro. Se te pide que, dada la longitud total máxima T que cabe en el ascensor, y las longitudes y los diámetros de las n piezas, descubras cuál es la lanza de mayor longitud t con t≤ T que puedes montar.

Entrada

Un juego de pruebas contiene varios casos. Cada caso se describe en varias líneas. La primera contiene dos naturales T y n, con 1≤ T ≤ 1000 y 1 ≤ n ≤ 100, que describen el máximo tamaño de lanza que te cabe en el ascensor y el número de piezas. A continuación vienen n líneas, cada una con un par de números di, li separados por espacios, que describen las n longitudes y diámetros en milímetros de las piezas. Se cumple que 1≤ di, li ≤ 1000.

Salida

Escribe, para cada caso, el tamaño t de la máxima lanza que quepa en el ascensor y que puedas formar usando las piezas del modo descrito.

Puntuación

  • Test1:  ‍40 Puntos ‍

    Resolver un juego de pruebas que contiene 100 situaciones con n ≤ 15, T ≤ 100, y donde los di son todos diferentes y se dan ordenados de mayor a menor diámetro (como el ejemplo 1).

  • Test2:  ‍60 Puntos ‍

    Resolver un juego de pruebas que contiene 100 situaciones de todo tipo.

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
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++