Conducta

Enunţ

O conductă este formată dintr-un ansamblu de $N$ țevi. Printr-o țeava poate trece o cantitate limitata de apa, fiecare țeava având capacitatea $C_i$. Cu alte cuvinte prin teava $i$ poate trece cel mult $C_i$ litri de apă.

Cerinţă

Știind că poți schimba capacitatea a cel mult o țeavă găsește numărul maxim de litri de apa pe care o poți transmite între cele două capete ale conductei înainte și după schimbare.

Date de intrare

Fișierul de intrare conducta.in conține pe prima linie conține numărul natural $P$, reprezentând cerința. A doua linie conține numărul natural $N$, reprezentând numărul de țevi din care este formată conducta. A treia linie conține $N$ numere naturale, $C_i$, reprezentand capacitatea conductei $i$.

Date de ieşire

Fișierul de ieșire conducta.out conține pe prima linie un număr natural, reprezentând răspunsul la cerința C. Dacă $P = 1$, se va afișa cantitatea de apă pe care o poți transmite între cele două capete fără a efectua vreo schimbare. Dacă $P = 2, se va afișa cantitatea de apă pe care o poți transmite între cele două capete modificând capacitatea a cel mult o țeavă.

Restricţii și precizări

• $2 \leq N \leq 10^5$
• $1 \leq C_i \leq 10^5$
• Pentru $50$ de puncte, $P = 1$, iar pentru alte $50$ de puncte $P = 2$

Exemple

conducta.in

1
10
3 6 11 40 11 3 8 8 10 4

conducta.out

3

conducta.in

2
10
3 9 3 15 1 26 2 7 12 4

conducta.out

2