Hide

Problem G
Almennir Borgarar

Languages en is
/problems/almennirborgarar/file/statement/is/img-0001.jpg
Mynd fengin af Unsplash
Í mörg ár hafa keppendur Forritunarkeppni Framhaldsskólanna fengið gómsæta hamborgara frá Hamborgarabúllu Tómasar í hádegismat. Keppendur mynda eina langa röð á meðan þeir bíða eftir borgurunum, en kokkar Búllunnar vinna hörðum höndum við að undirbúa borgarana. Kokkar Búllunnar eru mjög færir, og taka enga stund að undirbúa borgara. Eina undantekningin er að þeir þurfa að bíða eftir að borgararnir eldist á grillinu. Búllan er með $n$ lítil grill (númeruð frá $1$ til $n$), en hvert grill getur bara eldað einn borgara í einu. Grillin eru líka misheit og taka því mislangan tíma að elda borgara. Kokkarnir mældu þennan tíma og komust að því að grill númer $i$ tekur $t_ i$ sekúndur að elda einn borgara.

Nú bíður Benni spenntur í röðinni eftir að fá borgara, en það eru $m$ keppendur fyrir framan hann í röðinni. Ef kokkarnir nota grillin á sem bestan hátt, hvað er langt í að Benni fái borgarann sinn?

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ ($1 \leq n \leq 2\cdot 10^5$), fjöldi grilla, og $m$ ($0 \leq m \leq 10^9$), fjöldi keppenda fyrir framan Benna í röðinni.

Síðan kemur lína með $n$ heiltölum $t_1, t_2, \ldots , t_ n$, þar sem $t_ i$ ($1 \leq t_ i \leq 10^9$) er tíminn sem það tekur að elda borgara á grilli númer $i$.

Úttak

Skrifið út í hversu margar sekúndur Benni þarf að bíða áður en hann fær borgarann sinn, ef kokkarnir nota grillin á sem bestan máta.

Stigagjöf

Hópur

Stig

Takmarkanir

1

20

$n, m, t_ i \leq 100$

2

20

$n, m \leq 10^3$

3

20

$m, t_ i \leq 10^3$

4

10

$m \leq 10^5$

5

30

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
2 6
1 2
5
Sample Input 2 Sample Output 2
3 10
2 7 5
14
Sample Input 3 Sample Output 3
4 6
10 120 25 30
50