스시

스시

Sigríður는 이 나라에서 가장 인기 있는 스시 식당 중 하나인 Mæju-Sushi의 주인이다. Mæju-Sushi가 이토록 인기 있는 이유는 신비한 스시 팩 때문이다. 손님이 신비한 스시 팩을 사면 그 안에 무엇이 들어 있는지 전혀 알 수 없으며, 알고 있는 것은 가격이 $2^{i}$크로나인 팩을 사면 그 팩에 서로 다른 $i$가지 맛이 들어 있고 각 맛의 스시가 적어도 $k$개씩 들어 있다는 것뿐이다.

Sigríður는 팩을 최대한 비싼 가격에 팔 수 있도록 만드는 데 큰 어려움을 겪고 있다. Sigríður에게는 $a_1,a_2,\ldots,a_n$ 테이블 위에 순서대로 놓인 $n$개의 스시가 있으며, $a_i$는 $i$번째 스시의 맛을 나타낸다. Sigríður가 팩을 만들 때는 처음에는 비어 있는 새 상자를 하나 가져온 다음, 앞에 있는 스시를 몇 개 가져갈지 정한 뒤 상자를 닫고 다음 팩을 만들기 시작한다. 스시가 하나도 남지 않을 때까지 이 과정을 계속한다.

Sigríður가 스시를 최적으로 포장했을 때 모든 팩의 총가치가 최대 얼마가 될 수 있는지 구하여라.

팩에 서로 다른 $i$가지 맛이 들어 있고, 이 $i$가지 맛 중 어느 한 맛의 스시가 $k$개보다 적게 들어 있다면 그 팩의 가치는 $0$크로나가 된다.

채점

그룹 | 점수 | 제한

1 | 7 | $a_i = 1$ 및 $n \le 20$

2 | 21 | $n \le 20$

3 | 31 | $n \le 1\,000$

4 | 41 | 추가 제한 없음

첫째 줄에 두 정수 $n$와 $k$가 주어지며, $1 \le k \le n \le 10^5$

다음 줄에 $n$개의 정수 $a_1,a_2,\ldots,a_n$가 주어지며, $1 \le a_i \le 32$.

Sigríður가 스시를 최적으로 포장했을 때 얻을 수 있는 최대 금액을 나타내는 수 하나를 출력한다.