Las crecidas del Nilo
Enclavado en una zona principalmente desértica, el florecimiento y supervivencia durante milenios del Antiguo Egipto se debió principalmente al río Nilo. Sobre él ocurría un acontecimiento cíclico natural conocido como las crecidas del Nilo. Alimentado por las lluvias monzónicas del Macizo etíope, entre los meses de julio y noviembre el nivel del agua crecía significativamente, anegando las tierras alrededor de su orilla. Al retirarse el agua, la tierra quedaba impregnada de limo, un fertilizante natural que permitía la agricultura en una tierra que, de otro modo, sería desértica.
Entre noviembre y marzo los egipcios sembraban la cosecha, que recogían entre marzo y julio, justo antes de que el Nilo volviera a crecer. No es de extrañar que en el Antiguo Egipto el año se dividiera en tres estaciones (Akhet, "inundación", Peret, "germinación", y Shemu, "calor") y no en cuatro, como hacemos ahora.
La prosperidad del pueblo dependía completamente de la crecida. Hasta nuestros días ha llegado la historia de los siete años de vacas flacas por crecidas insuficientes que supusieron hambrunas. Una subida excesiva, por su parte, suponía destrucción. Hoy, las crecidas del Nilo han quedado en el pasado, tras la creación de la presa de Asuán, en la primera catarata del Nilo, que requirió un esfuerzo internacional titánico para trasladar monumentos antiguos a partes más altas y salvarlos de quedar bajo el agua del lago Nasser (en realidada un embalse gigante).
Dada la orografía del terreno alrededor del Nilo, ¿qué altura debe alcanzar éste para cubrir, al menos, la mitad de la superficie?
Entrada
Cada caso de prueba comienza con dos números, 1 ≤ C,F ≤ 100, indicando el ancho y alto del terreno que se quiere analizar. El número F siempre es impar.
A continuación aparecen F líneas, cada una con C números entre 0 y 1.000 indicando la altura del terreno en ese punto. Se considera que el agua del río Nilo entra por la celda central del lado izquierdo, que siempre será 0, la altura, nula, del lecho del río.
Salida
Por cada caso de prueba el programa escribirá la mínima altura que debe alcanzar el Nilo para conseguir anegar más de la mitad del terreno del caso de prueba, es decir más de la mitad de sus celdas. A continuación, en la misma línea, se indicará el número de celdas anegadas.
Se considera que una posición queda cubierta por el Nilo si éste alcanza la misma altura que el terreno en dicha posición. Ten en cuenta que para que una determinada posición quede cubierta, el agua debe poder llegar desde su punto de entrada (en el centro del lado izquierdo), atravesando zonas que no estén más altas que la crecida. El agua se desplaza en el mapa usando casillas adyacentes, pero no en diagonal.
Entrada de ejemplo
5 1 0 1 2 3 4 5 1 0 4 3 2 1 6 3 3 9 1 8 2 6 0 0 4 4 0 5 1 1 1 1 1 3
Salida de ejemplo
2 3 4 5 3 11