Problema número 472

Caminando voy

Tiempo máximo: 1,000-2,000 sMemoria máxima: 8192 KiB

Con la llegada del buen tiempo, el grupo de senderistas Caminando voy quiere preparar una serie de excursiones por la Sierra de Madrid. Las excursiones deben ser aptas para todos los socios (hay un numeroso grupo de jubilados y otro de niños de corta edad).

En concreto, se requiere que las cuestas arriba no se hagan demasiado penosas. Para ello, para cada excursión se ha confeccionado un perfil de desniveles, consistente en una secuencia de cotas de altura (valores enteros no negativos). Las cuestas arriba se corresponden con segmentos estrictamente crecientes, y el desnivel de una cuesta será la diferencia entre su cota más alta y su cota más baja. Una excursión se considerará apta si en todas las cuestas arriba el desnivel no supera un cierto valor estipulado D ≥ 0.

Por ejemplo, suponiendo D = 300, una excursión con el perfil de la izquierda sería apta, mientras que una con el perfil de la derecha no.

Perfil de dos excursiones

Ahora necesitan un programa que clasifique todas las excursiones que tienen programadas. ¿Puedes ayudarles?

Entrada

La entrada consta de una serie de casos de prueba, cada uno correspondiente a una excursión. Cada caso ocupa dos líneas. En la primera aparecen dos números separados por un espacio: el desnivel máximo permitido D (entre 0 y 1.000.000) y el número N (entre 1 y 200.000) de cotas de altura que forman la excursión. En la segunda línea aparecen las N cotas (números entre 0 y 1.000.000), separadas por espacios.

Salida

Para cada caso de prueba, el programa escribirá APTA si la excursión es apta para el desnivel máximo permitido, y NO APTA en caso contrario.

Entrada de ejemplo

300 11
1200 1250 1350 1400 1300 1600 1600 1600 1700 1500 1300
300 10
1200 1250 1350 1400 1550 1550 1550 1700 1500 1300
0 4
10 10 10 10

Salida de ejemplo

APTA
NO APTA
APTA