Start

2020-03-21 03:00 AKDT

Alfa 2020

End

2020-03-21 08:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 23:24:51

Time elapsed

5:00:00

Time remaining

0:00:00

Problem H
Sushi

/problems/iceland.sushi/file/statement/is/img-0001.jpg
Sushi

Sigríður er eigandi Mæju-Sushi sem er einn vinsælasti sushi staður á landinu. Mæju-Sushi er svona vinsælt útaf dularfullu sushi pökkunum þeirra. Þegar viðskiptavinur kaupir dularfullan sushi pakka hefur viðskiptavinurinn ekki hugmynd um hvað er í honum, eina sem hann veit er að ef hann kaupir pakka fyrir verð $2^{i}$ krónur að þá eru $i$ mismunandi bragðtegundir í pakkanum og allavega $k$ sushi af hverri bragðtegund.

Sigríður hefur verið í miklum vanda við að búa til pakka þannig það sé hægt að selja þá fyrir sem mestan pening. Sigríður hefur $n$ sushi röðuð á borð $a_1,a_2,\ldots ,a_ n$ þar sem $a_ i$ merkir bragðtegund $i$-ta sushi-sins. Þegar Sigríður býr til pakkana tekur hún nýjan kassa sem er upprunalega tómur, en svo getur hún valið hversu mörg af fremstu sushi-unum hún tekur áður en hún lokar og byrjar á næsta pakka. Svona gengur þetta koll af kolli þangað til ekkert sushi er eftir.

Getur þú sagt Sigríði hvert mesta virði pakkanna samtals gæti verið ef hún myndi pakka þeim á sem bestan hátt.

Ef pakki inniheldur $i$ mismunandi bragðtegundir og það er minna en $k$ sushi af einhverri af þessum $i$ bragðtegundum þá verður pakkinn virði $0$ krónur.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ þar sem $1 \le k \le n \le 10^5$
Næsta lína inniheldur $n$ heiltölur $a_1,a_2,\ldots ,a_ n$, þar sem $1 \le a_ i \le 32$.

Úttak

Skrifa á út eina tölu, mesta magn penings sem Sigríður getur eignast ef hún pakkar sushi-inu sem best.

Stigagjöf

Hópur

Stig

Takmarkanir

1

7

$a_ i = 1$ og $n \le 20$

2

21

$n \le 20$

3

31

$n \le 1\, 000$

4

41

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
7 2
1 1 2 2 3 1 3
8
Sample Input 2 Sample Output 2
8 1
1 2 3 4 1 1 2 3
26