La batalla por la Tierra Media
La batalla por la Tierra Media se acerca. Lo siento en el agua. Lo siento en la tierra. Lo huelo en el aire.
Para intentar defendernos ante la batalla inminente, Frodo, Merry, Pippin, Gandalf, Aragorn y todos los demás nos vamos a retirar a un campo de entrenamiento durante unas pocas semanas. El entrenamiento será duro, porque son muchas las criaturas a las que nos enfrentaremos.
Para tener alguna posibilidad de éxito, cada uno nos especializaremos en combatir contra un único tipo de critaura. Al entrenarnos en exclusividad esperamos salir victoriosos en todos los combates cuerpo a cuerpo que tengamos con sus individuos.
Ahora tenemos que decidir el tipo de criatura para el que nos entrenaremos cada uno. Para eso sabemos de cuántos especímenes de cada tipo dispone el enemigo y queremos hacer la asignación de forma que se minimice el número de individuos contra los que tendremos que luchar cada uno de nosotros.
Entrada
La entrada estará compuesta por distintos casos de prueba, cada uno ocupando dos líneas.
La primera línea de cada caso tendrá dos enteros. El primero indica cuántos somos los que vamos a luchar (1 ≤ n ≤ 106) y el segundo cuántos tipos de criaturas tiene el ejército enemigo (1 ≤ e ≤ 300.000, con e ≤ n).
En la segunda linea aparecen e enteros, uno por cada tipo de criatura, que indica cuántos individuos hay de cada una de ellas. Se garantiza que los números no serán superiores a 109.
Salida
Por cada caso de prueba se escribirá un único número que indica el número de enemigos al que se tendrá que enfrentar, en la mejor asignación posible, la persona de nuestro bando que tenga más enemigos asignados.
Como es lógico, la mejor asignación posible es aquella que minimiza esa cantidad.
Entrada de ejemplo
5 2 4 7 5 5 1 1 1 1 1 5 5 1 1 2 1 1
Salida de ejemplo
3 1 2
Notas
En el primer caso de prueba somos 5 combatiendo contra las 4+7 criaturas. Una posible asignación que minimiza los individuos totales a los que nos enfrentamos cada uno es la que entrena a dos de nosotros a luchar con las criaturas del primer tipo (tocaremos a 2 individuos cada uno) y a los otros tres los entrena contra el segundo tipo de criatura. Uno de estos últimos tendrá que luchar contra tres individuos.