Ir N ķēdes gabali. i-tais ķēdes gabals satur Li ķēdes posmus. Lai savienotu vairākus gabalus kopā, patvaļīgu ķēdes posmu drīkst atliekt un pēc tam saliekt atpakaļ.
Uzrakstiet programmu, kas dotam gabalu skaitam N un posmu skaitam katrā gabalā Li nosaka, kāds mazākais posmu skaits jāatliec/jāsaliec, lai visi gabali būtu apvienoti vienā ķēdē. Ķēdei nevar būt sazarojumi, t.i., katrs posms ir savienots tieši ar diviem citiem posmiem (izņemot gala posmus, kas ir savienoti tikai ar vienu citu posmu).
Teksta faila kede.dat pirmajā rindā dots vesels skaitlis N(2≤N ≤10000). Faila otrajā rindā doti N veseli skaitļi Li (1≤L i ≤1000000000) - ķēdes gabalu garumi. Katri divi blakus skaitļi ievaddatos ir atdalīti ar tukšumsimbolu.
Teksta faila kede.rez vienīgajā rindā jāizvada viens vesels skaitlis - mazākais posmu skaits, kas jāatliec un pēc tam jāaizliec, lai iegūtu vienu kopīgu ķēdi.
| kede.dat | kede.rez |
3 100 3 4 |
2 |