Pentru a diminua efectele crizei economice prin creşterea numărului de telespectatori (şi implicit a veniturilor provenite din publicitate), redacţia „Şocuri şi concursuri” a unei televiziuni selecte a decis să organizeze un turneu de lupte K1. La acesta vor lua parte sportivi. Fiecare dintre aceştia are un rating, calculat pe baza rezultatelor sale anterioare. Suma de bani pe care o primeşte pentru fiecare luptă la care va lua parte este egală cu acest rating. În urma fiecărei lupte rating-ul învingătorului creşte cu valoarea rating-ului învinsului.
Cerinţă
Cum televiziunea îşi doreşte un profit cât mai mare, conducătorii acesteia doresc să programeze meciurile astfel încât să plătească luptătorilor o sumă totală cât mai mică. Ştiind că nu există lupte încheiate la egalitate şi că turneul se termină doar după ce a fost stabilit un învingător, stabiliţi care este suma totală minimă pe care o pot plăti organizatorii. Suma totală plătită de televiziune este obţinută prin adunarea sumelor plătite tuturor luptătorilor pe parcursul turneului.
Date de intrare
Fişierul de intrare k1.in conţine pe prima linie o valoare , reprezentând numărul de luptători invitaţi la turneu, iar pe următoarele linii se află câte un număr natural nenul , reprezentând rating-ul iniţial al celui de-al -lea luptător.
Date de ieșire
Fişierul de ieşire k1.out conţine un singur număr natural , reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.
Restricții și precizări
- ;
Exemplu
k1.in
3
1
1
1
k1.out
5
Explicație
La prima luptă participă sportivi având fiecare rating-ul . În ultimul meci se vor întâlni un luptător cu rating-ul (învingătorul primului meci) şi altul cu rating (cel care nu a participat la prima luptă). Învingătorul primului meci primeşte în total ( pentru prima luptă şi pentru cea de a doua), cel care a pierdut prima luptă şi cel care a participat doar la ultima primesc câte , deci televiziunea va plăti în total .