Velocirráptors 201 P46713


Statement
 

pdf   zip

html

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 tT 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++