Velocirráptors 201 P46713

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 $l_i$ y un diámetro $d_i$. 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\leq 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\leq T \leq 1000$ y $1 \leq n \leq 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 $d_i$, $l_i$ separados por espacios, que describen las $n$ longitudes y diámetros en milímetros de las piezas. Se cumple que $1\leq d_i, l_i \leq 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:

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

• Test2:

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