Problem H
Sushi
Languages
en
is
Sigríður is the owner of Mæju-Sushi which is one of the most popular sushi places in the country. Mæju-Sushi got this popular thanks to their mystery sushi packages. When a customer purchases a mystery sushi package, they have no idea what’s in it, they only know that if they buy a package for $2^ i$ króna then there are $i$ different flavor profiles in the package and at least $k$ sushi pieces of each flavor profile.
Sigríður has been having some issues creating these packages such that they can be sold for maximum profit. Sigríður has $n$ sushi $a_1, a_2, \dots , a_ n$ arranged on a table where $a_ i$ denotes the flavor profile of the $i$-th sushi. When Sigríður makes a package she takes a new, initially empty box, then decides how many sushi pieces to take from the front of the row and put in the box. She then closes the box and starts her work on the next package. This continues until there is no sushi left to package.
Could you tell Sigríður what the sushi could sell for at most if she packages them optimally?
If a package contains $i$ different flavor profiles and there are less than $k$ sushi of one of these flavor profiles the package will be worth $0$ krónur.
Input
The first line contains two integers $n$ and $k$ where $1 \leq k \leq n \leq 10^5$. The next line contains $n$ integers $a_1,a_2,\dots ,a_ n$ where $1 \leq a_ i \leq 32$.
Output
Print a single integer, the maximum number of króna Sigríður can earn if she packages the sushi optimally.
Scoring
|
Group |
Points |
Constraints |
|
1 |
7 |
$a_ i = 1$ and $n \leq 20$ |
|
2 |
21 |
$n \leq 20$ |
|
3 |
31 |
$n \leq 1\, 000$ |
|
4 |
41 |
No further constraints |
| 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 |
