El de la búsqueda binaria P89178

Estás de vacaciones en Estados Unidos, en una autopista en medio de la nada (pongamos, por ejemplo, Ohio), conduciendo uno de esos cochazos donde cabría un equipo de futbol americano entero. Aburrido, decides descubrir a qué velocidad constante debes mantener para alcanzar la siguiente gasolinera lo antes posible. Recuerda: a mayor velocidad, mayor consumo, por lo que si al llegar a la gasolinera te queda carburante, es que no ibas lo bastante rápido [Footnote: La OIE recomienda una conducción responsable en la vida real.].

En particular, sabes que tu vehículo consume

mililitros de carburante para recorrer un kilómetro, donde 0<v<30000 y −3000<w<3000 es la velocidad del vehículo y la fuerza del viento en centímetros por segundo, y los símbolos ⌊ · ⌋ quieren decir redondeo hacia abajo. (Ciertamente, estos coches americanos consumen mucho).

Se te pide que, dada la cantidad de carburante que tienes, el número de kilómetros que te separa de la gasolinera, y la intensidad del viento en cada uno de los kilómetros, digas a qué velocidad en centímetros por segundo deberías hacer todo el viaje para llegar lo antes posible a la gasolinera, sin quedarte sin carburante por el camino.

Entrada

Un juego de pruebas contiene varios casos, separados entre sí por una línea en blanco. Un caso viene descrito por varias líneas. La primera contiene dos números C<10⁹ y n<10³, separados por espacios, que describen la cantidad de carburante que tienes y el número de tramos que te separan de la gasolinera. Las siguientes n líneas describen un tramo de carretera, formado por un par de números d_i y w_i, con la longitud en kilómetros y la fuerza del viento en el tramo i-ésimo. Se cumple que ∑_i=1ⁿ d_i < 10⁵. El consumo de carburante en cada kilómetro de un tramo debe calcularse individualmente, a efectos de los redondeos.

Salida

Para cada caso, escribe en una línea la velocidad en centímetros por segundo que te permitiría llegar antes a la gasolinera sin quedarte sin carburante por el camino. Se te garantiza que este numero es mayor que 0 y menor que 30000.

Pista: Búsqueda binaria es aquel invento que nos permite encontrar una palabra en el diccionario sin tener que leerlas todas.

Autor: Ricardo Martín, Omer Giménez.