Coda#3004
In una stazione ferroviaria ci sono biglietterie, ma una sola coda comune che conduce ad esse. Il processo di servizio avviene nel modo seguente:
Inizialmente, quando tutte le casse sono libere, le prime persone della coda occupano le casse. I restanti clienti attendono in coda. Non appena una cassa si libera dopo aver servito un cliente, il successivo in coda occupa quel posto. Il processo continua finché tutti i clienti non sono stati serviti.
Determinare il tempo minimo necessario per servire tutti i clienti.
La prima riga contiene due numeri interi: la dimensione della coda e il numero di biglietterie (1 \le n \le 10^5, 1 \le k \le 10^4).
La seconda riga contiene numeri interi positivi t_i (1 \le t_i \le 10^5) — il tempo di servizio dell'-esimo cliente.
Stampare un singolo numero intero — il tempo minimo necessario per servire l'intera coda.
Esempio 1
Esempio 2