Problem
Handsome Jack quiere establecer sus propias plantas de procesamiento de Eridium.
Hay n fábricas bajo el control de Jack, cada una de ellas está numerada del 1 al n. Cada planta está ubicada en el depósito de Eridium, donde también se extrae en combinación. Y cuanto mayor sea el número de fábrica, más nuevo es.
Cada planta tiene su índice de eficiencia a
i. Puede ser positivo, negativo o cero.
Cada planta debe procesar el mineral de Eridium. Puede usar su propio depósito o tomar mineral, procesado en el pasado por otra planta, a través de la tubería. Sin embargo, este proceso es algo limitado. En primer lugar, con el fin de no sobrecargar el sistema de tuberías, cada planta puede aceptar el mineral para su posterior procesamiento estrictamente entre sí (o no aceptar y utilizar su propio depósito). En segundo lugar, las plantas más antiguas no son técnicamente capaces de reprocesar el mineral después de una planta más nueva.
El rendimiento final de todo el sistema se calcula de la siguiente manera: para cada planta, se toma su eficiencia a
i y se multiplica por la etapa de procesamiento, que se calcula como el número de veces que se procesa el mineral entrante. (para más detalles, consulte las explicaciones de los ejemplos), luego se resumen todos los valores obtenidos para todas las plantas.
Ayuda a Handsome Jack a organizar el sistema para que el rendimiento general de todo el sistema sea lo más alto posible.
Entrada:
La primera línea contiene un número natural n (1 <= n <= 7) - el número de fábricas.
La segunda línea contiene n enteros separados por espacios, donde el i-ésimo número es a
i (-1000 <= a
i <= 1000) - la eficiencia base de la planta bajo el número i.
Salida:
Imprima un solo número: el rendimiento total máximo posible de todo el sistema.
Ejemplos:
| Entrada |
Salida |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Explicaciones:
En el primer ejemplo, es más rentable que la primera planta extraiga su propio mineral, que la segunda planta reciba el mineral de la primera y que la tercera reciba del segundo. En este caso, la primera planta realiza procesamiento primario y su productividad es 1 * 1 = 1. La segunda planta realiza procesamiento secundario, su productividad es 5 * 2 = 10. Y la tercera planta procesa el mineral recibido por tercera vez, entonces su productividad es 3 * 3 = 9. El rendimiento total es 1 + 10 + 9 = 20.
Tenga en cuenta que en este ejemplo, la segunda y la tercera planta no se pueden intercambiar porque la segunda planta no podrá procesar mineral después de la tercera por razones técnicas, porque es más antigua que la tercera.
En el segundo ejemplo, la primera y la tercera fábrica utilizarán sus depósitos y la segunda fábrica recibirá el mineral de la primera.