Terminando los chalets
La urbanización de chalets está ya casi terminada. Solo queda que terminen sus tareas el electricista y el fontanero que, eso sí, se llevan bastante mal por lo que no pueden coincidir trabajando en el mismo chalet a la vez.
El tiempo que ambos necesitan en cada casa es el mismo pues depende exclusivamente de los metros construidos que tengan y da igual cuál de los dos haga la instalación antes, pues ninguno necesita que la parte del otro esté acabada para hacer la suya. Eso sí, lo que no pueden hacer es dejar las cosas a medias: cuando entran a trabajar en un chalet no pasarán a otro hasta que no terminen en ese.
Teniendo en cuenta que el orden en el que se van terminando los chalets no es importante, debemos decidir el orden en el que cada uno hará su trabajo para que las obras de todos los chalets terminen cuanto antes.
Entrada
La entrada está compuesta por un número indeterminado de casos de prueba, cada uno ocupando dos líneas.
La primera línea de cada caso tiene el número N de chalets que hay que terminar (hasta 106). En la segunda línea aparecen N enteros con el tiempo que necesita trabajar tanto el fontanero como el electricista en cada chalet (números entre 0 y 1012).
Salida
Por cada caso de prueba se escribirá la cantidad de tiempo necesario para terminar la construcción de todos los chalets.
Entrada de ejemplo
2 10 15 3 5 10 5
Salida de ejemplo
30 20