Problem
Le beau Jack veut créer ses propres usines de transformation d'Eridium.
Il y a n usines sous le contrôle de Jack, chacune d'elles est numérotée de 1 à n. Chaque usine est située au gisement Eridium, où elle est également exploitée en combinaison. Et plus le numéro d'usine est élevé, plus il est récent.
Chaque usine a son indice d'efficacité a
i. Il peut être positif, négatif ou nul.
Chaque usine doit traiter le minerai d'Eridium. Vous pouvez utiliser votre propre gisement ou prendre du minerai, traité dans le passé par une autre usine, à travers le pipeline. Cependant, ce processus est quelque peu limité. Premièrement, afin de ne pas surcharger le système de pipelines, chaque usine peut accepter le minerai pour un traitement ultérieur strictement l'une de l'autre (ou ne pas accepter et utiliser son propre gisement). Deuxièmement, les usines plus anciennes ne sont techniquement pas capables de retraiter le minerai après une usine plus récente.
La performance finale de l'ensemble du système est calculée comme suit : pour chaque usine, son efficacité a
i est prise et multipliée par l'étape de traitement, qui est calculée comme le nombre de fois où le minerai entrant est traité (pour plus de détails, voir les explications des exemples), puis toutes les valeurs obtenues sont résumées pour toutes les plantes.
Aidez Handsome Jack à organiser le système afin que les performances globales de l'ensemble du système soient aussi élevées que possible.
Saisie :
La première ligne contient un nombre naturel n (1 <= n <= 7) - le nombre d'usines.
La deuxième ligne contient n entiers séparés par des espaces, où le i-ème nombre est a
i (-1000 <= a
i <= 1000) - l'efficacité de base de l'usine sous le numéro i.
Sortie :
Imprimez un seul numéro - la performance totale maximale possible de l'ensemble du système.
Exemples :
| Entrée |
Sortie |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Explications :
Dans le premier exemple, il est plus rentable que la première usine extraie son propre minerai, que la deuxième usine reçoive du minerai de la première et que la troisième reçoive du minerai de la seconde. Dans ce cas, la première usine effectue le traitement primaire et sa productivité est de 1 * 1 = 1. La deuxième usine effectue le traitement secondaire, sa productivité est de 5 * 2 = 10. Et la troisième usine traite le minerai reçu pour la troisième fois, donc sa productivité est de 3 * 3 = 9. La performance totale est de 1 + 10 + 9 = 20.
Veuillez noter que dans cet exemple, les deuxième et troisième plantes ne peuvent pas être échangées, car la deuxième usine ne pourra pas traiter le minerai après la troisième pour des raisons techniques, car elle est plus ancienne que la troisième.
Dans le deuxième exemple, les première et troisième usines utiliseront leurs gisements et la deuxième usine recevra le minerai de la première.