Problem
Handsome Jack mahu menubuhkan kilang pemprosesan Eridium sendiri.
Terdapat n kilang di bawah kawalan Jack, setiap satu daripadanya bernombor dari 1 hingga n. Setiap tumbuhan terletak di deposit Eridium, di mana ia juga dilombong dalam kombinasi. Dan semakin tinggi nombor kilang, semakin baharu ia.
Setiap loji mempunyai indeks kecekapan a
i. Ia boleh menjadi positif, negatif atau sifar.
Setiap tumbuhan mesti memproses bijih Eridium. Anda boleh menggunakan deposit anda sendiri atau mengambil bijih, diproses pada masa lalu oleh loji lain, melalui saluran paip. Walau bagaimanapun, proses ini agak terhad. Pertama, untuk tidak membebankan sistem saluran paip, setiap loji boleh menerima bijih untuk pemprosesan selanjutnya secara ketat antara satu sama lain (atau tidak menerima dan menggunakan depositnya sendiri). Kedua, loji yang lebih tua secara teknikal tidak mampu memproses semula bijih selepas loji yang lebih baharu.
Prestasi akhir keseluruhan sistem dikira seperti berikut: untuk setiap loji, kecekapannya a
i diambil dan didarab dengan peringkat pemprosesan, yang dikira sebagai bilangan masa bijih yang masuk diproses (untuk butiran lanjut, lihat penjelasan untuk contoh), kemudian semua nilai yang diperolehi diringkaskan untuk semua tumbuhan.
Bantu Handsome Jack menyusun sistem supaya prestasi keseluruhan keseluruhan sistem adalah setinggi mungkin.
Input:
Baris pertama mengandungi nombor asli n (1 <= n <= 7) - bilangan kilang.
Baris kedua mengandungi n integer yang dipisahkan ruang, dengan nombor ke-i ialah a
i (-1000 <= a
i <= 1000) - kecekapan asas tumbuhan di bawah nombor i.
Output:
Cetak satu nombor - jumlah prestasi maksimum yang mungkin bagi keseluruhan sistem.
Contoh:
| Input |
Output |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Penjelasan:
Dalam contoh pertama, adalah paling menguntungkan untuk loji pertama melombong bijihnya sendiri, loji kedua menerima bijih dari yang pertama, dan yang ketiga menerima dari yang kedua. Dalam kes ini, loji pertama melakukan pemprosesan primer dan produktivitinya ialah 1 * 1 = 1. Loji kedua melakukan pemprosesan sekunder, produktivitinya ialah 5 * 2 = 10. Dan loji ketiga memproses bijih yang diterima untuk kali ketiga, jadi produktivitinya ialah 3 * 3 = 9. Jumlah prestasi ialah 1 + 10 + 9 = 20.
Sila ambil perhatian bahawa dalam contoh ini, tumbuhan kedua dan ketiga tidak boleh ditukar, kerana loji kedua tidak akan dapat memproses bijih selepas yang ketiga atas sebab teknikal, kerana ia lebih tua daripada yang ketiga.
Dalam contoh kedua, kilang pertama dan ketiga akan menggunakan deposit mereka, dan kilang kedua akan menerima bijih daripada yang pertama.