Problemi 11

Kërkesa

Xheni dhe Ylli ishin të gëzuar për festat që po afronin dhe do punonin sëbashku për përgatitjet e nevojshme. Janë N punë për tu kryer. Për një punë i Xhenit i duhen \(X_i\) sekonda kurse Yllit i duhen \(Y_i\) sekonda. Ata vendosën që ti bënin punët në mënyrë të alternuar. Nqs punën e parë e bën Xheni, punën e dytë e bën Ylli (ndërkohë që Xheni shlodhet), punën e tretë e bën prapë Xheni, e kështu me radhë. Nqs punën e parë e bën Ylli, të dytën e bën Xheni, e kështu me radhë.

Na jepen kohët që i duhen Xhenit dhe Yllit për çdo punë, gjeni kohën më të vogël që u duhet për ti mbaruar të gjitha punët.

Referenca: https://www.codechef.com/problems/XENTASK

Shembull

$ cat input.txt
1
3
2 1 2
3 2 1

$ python3 prog.py < input.txt
5

Nqs punën e parë do ta bëjë Xheni do duhen 2+2+2=6 sekonda. Kurse po ta bëjë Ylli punën e parë do duhen 3+1+1=5 sekonda. Koha më e vogël është 5 sekonda.