Problem
Il bel Jack vuole creare i propri impianti di lavorazione dell'eridio.
Ci sono n fabbriche sotto il controllo di Jack, ognuna numerata da 1 a n. Ogni pianta si trova nel deposito di Eridium, dove viene anche estratta in combinazione. E più alto è il numero di fabbrica, più recente è.
Ogni impianto ha il suo indice di efficienza a
i. Può essere positivo, negativo o zero.
Ogni impianto deve elaborare il minerale di eridio. Puoi utilizzare il tuo deposito o prendere il minerale, lavorato in passato da un altro impianto, attraverso la pipeline. Tuttavia, questo processo è alquanto limitato. In primo luogo, per non sovraccaricare il sistema di condotte, ogni impianto può accettare il minerale per l'ulteriore lavorazione rigorosamente l'uno dall'altro (oppure non accettare e utilizzare il proprio deposito). In secondo luogo, gli impianti più vecchi non sono tecnicamente in grado di rielaborare il minerale dopo un impianto più nuovo.
La prestazione finale dell'intero sistema è calcolata come segue: per ogni impianto, la sua efficienza a
i è presa e moltiplicata per la fase di lavorazione, che è calcolata come il numero di volte in cui il minerale in entrata viene lavorato (per maggiori dettagli, vedere le spiegazioni per gli esempi), quindi vengono riepilogati tutti i valori ottenuti per tutte le piante.
Aiuta Jack il Bello a organizzare il sistema in modo che le prestazioni complessive dell'intero sistema siano le più elevate possibili.
Inserimento:
La prima riga contiene un numero naturale n (1 <= n <= 7) - il numero di fabbriche.
La seconda riga contiene n numeri interi separati da spazio, dove l'i-esimo numero è a
i (-1000 <= a
i <= 1000) - l'efficienza di base dell'impianto di cui al numero i.
Uscita:
Stampa un singolo numero: la massima prestazione totale possibile dell'intero sistema.
Esempi:
| Input |
Uscita |
3
153
| 20 |
3
1 5 -3 |
8 |
Spiegazioni:
Nel primo esempio, è più vantaggioso che il primo impianto estragga il proprio minerale, il secondo impianto riceva minerale dal primo e il terzo riceva dal secondo. In questo caso, il primo impianto esegue la lavorazione primaria e la sua produttività è 1 * 1 = 1. Il secondo impianto esegue la lavorazione secondaria, la sua produttività è 5 * 2 = 10. E il terzo impianto elabora il minerale ricevuto per la terza volta, quindi la sua produttività è 3 * 3 = 9. La performance totale è 1 + 10 + 9 = 20.
Si prega di notare che in questo esempio, la seconda e la terza pianta non possono essere scambiate, perché il secondo impianto non sarà in grado di lavorare il minerale dopo il terzo per motivi tecnici, perché è più vecchio del terzo.
Nel secondo esempio, la prima e la terza fabbrica utilizzeranno i loro depositi e la seconda fabbrica riceverà il minerale dalla prima.