Într-o gară se află un tren
cu 2nvagoane.
Pentru fiecare vagon se cunoaşte numărul de călători care urmează să se
urce. Astfel la etapa 1 avem acest tren. La etapa 2 se formează din trenul
de la etapa 1 două trenuri, unui cu vagoanele de pe poziţii impare, iar
celălalt cu vagoanele de pe poziţii pare. La etapa 3, din fiecare tren
de la etapa 2 se formează câte două trenuri: unul cu vagoanele de pe poziţii
pare, iar celălalt cu cele de pe poziţii impare şi aşa mai departe. Astfel
la etapa k
din fiecare tren de la etapa k-1
se construiesc câte două trenuri, unul cu vagoanele de pe poziţii impare,
iar celălalt cu vagoanele de pe poziţii pare.
Cerinţă
Să se scrie un program care pentru k
dat, determină numărul maxim de călători aflaţi într-unul dintre trenurile
etapei k.
Date de intrare
Fişierul de intrare tren.in
are pe prima linie numerele naturale n
şi k separate
printr-un spaţiu. Pe cea de a doua linie se afla n
numere naturale separate prin spatii; al i-lea
numar de pe linie reprezinta numarul de calatori din vagonul de pe pozitia
i (1<=i<=n).
Date de ieşire
Fişierul de ieşire tren.out va conţine pe prima
linie numărul cerut.
Restricţii
0 <= n < 11
0 < k < n+2
Numărul de călători din trenul iniţial (etapa
1) este <2000000001.
Exemple
tren.in
tren.out
Explicaţii
3 3
10 20 30 25 15 5 10 45
70
La etapa 2 avem doua trenuri cu
vagoanele date de numarul de calatori:
10 30 15 10
20 25 5 45
La etapa 3 avem 4 trenuri cu vagoanele date de numarul de calatori:
10 15
30 10
20 5
25 45
La aceasta etapa trenul cu numarul maxim de calatori (70) este format
din doua vagoane care au fiecare cate 25, respectiv 45 calatori.