FMI NO STRESS 13 | Mega

"Scoateți ultimul produs. Așezați la loc ultimul produs. Scoateți ultimul produs. Un operator va veni să vă asiste."

Cerință

Costel face cumpărăturile la Mega. El acum se află în fața a $N$ case de marcat self-check și are $M$ oameni în fața lui la coadă. Pentru fiecare cumpărător $i$ se cunoaște timpul $t_{i}$ în care își termină checkout-ul. Coada se mișcă în felul următor:

• Primii $N$ oameni de la coadă ocupă primele $N$ case de marcat
• Aceștia își realizează checkout-ul în paralel, iar cumpărătorul $i$ ocupă o casă de marcat timp de $t_i$ minute
• Atunci când un cumpărător termină de făcut checkout-ul, acesta pleacă și îi ia locul următorul de la coadă (timpul necesar acestei schimbări poate fi neglijat, adică se întâmplă instant)

Se cere să se afle după cât timp ajunge Costel la o casă de marcat.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $M$. Pe următoarea linie se găsesc $M$ numere, reprezentând timpii în care oamenii de la coadă își fac checkout-ul.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, timpul după care ajunge Costel la o casă de marcat.

Restricții și precizări

• $1 \leq N, M \leq 200\ 000$;
• $1 \leq t_i \leq 1\ 000\ 000\ 000$;
• Pentru teste în valoare de $6$ puncte, $M < N$;
• Pentru alte teste în valoare de $8$ puncte, $M = N$;
• Pentru alte teste în valoare de $4$ puncte, $N = 1$;
• Pentru alte teste în valoare de $13$ puncte, $t_i$ sunt egale pentru oricare $1 \leq i \leq M$;
• Pentru alte teste în valoare de $27$ de puncte, $M \leq 2\ 000$;
• Pentru alte teste în valoare de $42$ de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

2 7
1 6 3 2 3 5 4

stdout

11

Explicație

Sunt 2 case de marcat, iar coada este formată din $7$ oameni ($8$ cu tot cu Costel). Acțiunea se desfășoară în felul următor:

Exemplul 2

stdin

3 2
10000 10000

stdout

0

Explicație

Sunt $3$ case de marcat, dar $2$ oameni la coadă ($3$ cu tot cu Costel). Toți $3$ pot ocupa din prima casele de marcat, deci Costel nu va aștepta niciun minut până își face checkout-ul.