Problem
Yakışıklı Jack kendi Eridium işleme tesislerini kurmak istiyor.
Jack'in kontrolü altında n fabrika vardır ve her biri 1'den n'ye kadar numaralandırılmıştır. Her bitki, kombinasyon halinde çıkarıldığı Eridyum yatağında bulunur. Ve fabrika numarası ne kadar yüksekse, o kadar yenidir.
Her tesisin verimlilik endeksi a
i'dir. Pozitif, negatif veya sıfır olabilir.
Her fabrika Eridium cevherini işlemelidir. Boru hattı aracılığıyla kendi yatağınızı kullanabilir veya geçmişte başka bir tesiste işlenmiş cevheri alabilirsiniz. Ancak bu süreç biraz sınırlıdır. İlk olarak, boru hattı sistemini aşırı yüklememek için, her tesis kesinlikle birbirinden daha ileri işleme için cevher kabul edebilir (veya kabul etmeyebilir ve kendi yatağını kullanabilir). İkinci olarak, daha eski tesisler teknik olarak cevheri yeni bir tesisten sonra yeniden işleyemez.
Tüm sistemin nihai performansı şu şekilde hesaplanır: her tesis için verimliliği a
i alınır ve gelen cevherin işlenme sayısı olarak hesaplanan işleme aşaması ile çarpılır. (daha fazla ayrıntı için örnekler için açıklamalara bakın), ardından elde edilen tüm değerler tüm bitkiler için özetlenir.
Yakışıklı Jack'in tüm sistemin genel performansının olabildiğince yüksek olmasını sağlamak için sistemi düzenlemesine yardım edin.
Giriş:
İlk satır n (1 <= n <= 7) doğal sayısını içerir - fabrikaların sayısı.
İkinci satır n boşlukla ayrılmış tam sayı içerir, burada i'inci sayı a
i (-1000 <= a
i <= 1000) - temel verimliliktir i numarası altındaki fabrikanın.
Çıktı:
Tek bir sayı yazdırın - tüm sistemin mümkün olan maksimum toplam performansı.
Örnekler:
| Giriş |
Çıktı |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Açıklamalar:
Birinci örnekte, birinci tesisin kendi cevherini çıkarması, ikinci tesisin birinciden cevher alması ve üçüncünün ikinciden alması en karlı olanıdır. Bu durumda birinci tesis birincil işleme yapmaktadır ve verimliliği 1 * 1 = 1'dir. İkinci tesis ikincil işlem yapmaktadır, verimliliği 5 * 2 = 10'dur. Ve üçüncü tesis alınan cevheri üçüncü kez işler, yani üretkenliği 3 * 3 = 9'dur. Toplam performans 1 + 10 + 9 = 20'dir.
Lütfen bu örnekte ikinci ve üçüncü bitkilerin değiştirilemeyeceğini unutmayın, çünkü ikinci tesis teknik nedenlerle üçüncüden sonra cevher işleyemeyecek, çünkü üçüncüden daha eski.
İkinci örnekte, birinci ve üçüncü fabrikalar yataklarını kullanacak ve ikinci fabrika birinciden cevher alacaktır.