Velocirráptor ruso P78006

Te dispones a tomar la montaña rusa cuando te das cuenta que un velocirráptor está corriendo en línea recta hacia ti. Por suerte, tienes una vía de escape: la propia montaña rusa. Sabes que el velocirráptor te podrá seguir por la vía, pero que no cabrá por el túnel de la montaña rusa. Empiezas a empujar el vagón por el andén, mientras el velocirráptor te persigue. Por razones obvias quieres montarte cuanto antes en el vagón: deseas conseguir la suficiente velocidad como para llegar hasta el túnel y deshacerte del velocirráptor, pero no quieres empujar más de lo estrictamente necesario por si te atrapa en el propio andén.

Conoces de memoria cada una de las subidas y bajadas que tiene la montaña rusa. Además, sabes que por cada metro en vertical que se sube, el vagón pierda una velocidad de K kilómetros por hora, mientras que por cada metro en vertical que baja, recupera la misma velocidad de K kilómetros por hora perdida (las leyes de la física no se cumplen a rajatabla en los parques de atracciones; si no, no tendría sentido pagar tanto por entrar a ellos). Sabes también que no se pierde velocidad por el rozamiento con la vía, y que es aceptable que el vagón tenga velocidad 0 durante algún momento del recorrido (con un pequeño impulso por tu parte el vagón seguiría avanzando hacia adelante) pero que en ningún momento puede tener velocidad negativa.

Entrada

La primera línea del juego de pruebas contiene el número de casos a resolver. Cada caso empieza con 3 enteros N, X y K en una línea, donde N es el número de tramos de la atracción, X es la coordenada x del punto donde se encuentra el túnel, y K es la velocidad en kilómetros por hora que se pierde (respectivamente, se gana) por cada metro subido (respectivamente, bajado) en vertical. Las siguientes N+1 líneas contienen N+1 pares de coordenadas (x_i,y_i), separados por un espacio, que describen los extremos de los N tramos rectos de los que se compone la atracción. Se cumple que (x₁,y₁) es siempre (0,0), y que los x_i son estrictamente crecientes, es decir, x_i < x_i+1. Además, el túnel siempre coincide con el inicio de algún tramo de la montaña rusa, es decir, existe un punto x_i con 1<i≤ N tal que x_i = X.

Salida

Para cada caso, escribe en una línea la velocidad mínima en kilómetros por hora con la que debes salir del andén para alcanzar el inicio del túnel, garantizando que durante todo el trayecto la velocidad del vagón es mayor o igual que 0.

Puntuación

• TestA:  ‍ Pruebas con no más de 20 casos donde N ≤ 15 y X ≤ 1000.  ‍30 Puntos ‍

• TestB:  ‍ Pruebas con no más de 20 casos donde N ≤ 25000 y X ≤ 10⁶.  ‍70 Puntos ‍