El carpintero Ebanisto
El carpintero Ebanisto ha recibido el encargo de cortar un tablón en varios trozos que han sido previamente marcados sobre la madera. El esfuerzo de cortar un tablón de madera en dos es el doble de su longitud.
Ebanisto se ha dado cuenta de que el orden en el que realice los cortes en el tablón influye en el esfuerzo empleado. Por ejemplo, supongamos que un tablón de 10 metros de longitud tiene que cortarse a 3, 6 y 8 metros de uno de los extremos. Una posibilidad sería cortar primero por la marca de los 3 metros, luego por la marca de los 6 metros y finalmente por la de 8 metros, lo que le costaría a Ebanisto un esfuerzo total de 2×10 + 2×7 + 2×4 = 42. Sin embargo, si corta primero por la marca del 6, después por la del 3 y finalmente por la del 8, entonces le costaría un esfuerzo de 2×10 + 2×6 + 2×4 = 40.
¿Puedes ayudar a Ebanisto a averiguar en qué orden cortar el tablón por las marcas para minimizar el esfuerzo realizado?
Entrada
La entrada constará de varios casos de prueba. La primera línea de cada caso contendrá dos números positivos: L (entre 10 y 1.000.000), que representa la longitud del tablón que debemos cortar; y N (entre 1 y 500), que indica el número de cortes que se deben realizar. La siguiente línea contendrá N números positivos ci (0 < ci < L), que determinan los puntos en los que se deben realizar los cortes, dados en orden creciente.
La entrada termina con 0 0.
Salida
Para cada caso de prueba se debe escribir el mínimo esfuerzo que debe realizar Ebanisto para realizar todos los cortes.
Entrada de ejemplo
10 3 3 6 8 20 4 8 10 15 17 0 0
Salida de ejemplo
40 88