Problema número 496

La estación de esquí

Tiempo máximo: 1,000-4,000 sMemoria máxima: 16384 KiB
Dos esquiadores planificando su ruta en los Alpes

A Andrés le encanta esquiar. A veces necesita ir de un punto a otro de la estación en un tiempo determinado y, como buen esquiador, siempre busca la ruta que le permita conseguirlo maximizando los metros de descenso.

Este año ha ido a una estación muy grande de los Alpes y necesita ayuda para encontrar las mejores rutas.

Entrada

La entrada está formada por distintos casos de prueba, cada uno compuesto por varias líneas.

La primera línea contiene un único número entero N, que representa el número de remontes mecánicos (sólo de subida) en la estación. A continuación aparecen N líneas que describen cada uno de los N remontes. En cada una aparecen tres números enteros: la altura en metros del punto inicial del remonte (I), la altura en metros del punto final del remonte (F) y el tiempo en segundos que se tarda en subir (T, incluye el posible tiempo de espera haciendo cola). La última línea contiene 3 números enteros: la altura del punto de salida de Andrés (O), la altura del punto de destino (D), y el tiempo máximo en segundos para llegar (M). Se supone que Andrés siempre se puede desplazar hacia abajo esquiando, a razón de un segundo por cada metro de desnivel.

Se cumple 1 ≤ N ≤ 25, 0 ≤ OD ≤ 3.000 y 0 < M ≤ 10.000. Para cada remonte se tiene 0 ≤ I < F ≤ 3.000 y 500 ≤ T ≤ 2.000.

El final de la entrada se indica con una línea con un único cero que no se debe procesar.

Salida

Para cada caso de prueba, se escribirá una línea indicando los metros de bajada de la mejor solución (aquella que consigue ir desde el punto de origen al punto de destino en un tiempo menor o igual que el indicado y maximiza los metros de bajada). Si es imposible llegar al destino en el tiempo indicado se imprimirá la palabra IMPOSIBLE.

Entrada de ejemplo

3
0 100 500
0 300 1000
200 400 500
0 300 5000
3
0 100 500
0 300 1000
200 400 500
0 400 1700
3
0 100 500
0 300 1000
200 400 500
0 400 1300
0

Salida de ejemplo

1000
100
IMPOSIBLE