팝 음악

라데우시는 팝 음악을 좋아한다. 팝 음악은 마음을 편하게 해 주고, 춤추기에 좋으며, 프로그래밍에도 도움이 된다. 하지만 이런 장점은 모두 멜로디와 박자가 잘 맞아야 살아난다. 폴란드어에서 「bit」와 「beat」는 같은 단어라서 원문이 거기서는 더 재미있지만, 영어에서는 그런 말장난이 잘 통하지 않는다. 미안하다!

라데우시는 방금 새 멜로디를 만들었고, 여기에 좋은 박자를 맞추려 한다. 멜로디는 $n$초 동안 이어진다. $i$번째 초의 품질은 정수 $a_i$이며, 음수일 수도 있다. 그는 음이 아닌 정수 $b_i$, 즉 박자 이득 계수를 골라야 한다. 계수는 $i$번째 초를 $C(b_i)$배로 강화한다. 여기서 $C(b_i)$는 $b_i$의 이진 표현에 들어 있는 1의 개수이다. 예를 들어 $b_i = 13$이면 3배의 이득을 얻는다. 13은 이진수로 1101이고 1이 세 개 들어 있기 때문이다.

곡의 최종 품질은 다음과 같다. $a_1 \cdot C(b_1) + a_2 \cdot C(b_2) + \ldots + a_n \cdot C(b_n).$

박자 이득 계수는 $m$ 이하의 음이 아닌 정수로 이루어진 증가하는 수열이어야 한다. $0 \le b_1 < b_2 < \ldots < b_n \le m.$

라데우시는 최종 품질이 최대가 되도록 계수를 고르려 한다. 그가 얻을 수 있는 최댓값은 얼마인가?

첫째 줄에 두 정수 $n$, $m$ ($1 \le n \le 200$, $n - 1 \le m \le 10^{18}$)이 주어진다. 각각 곡의 길이(초)와 박자 이득 계수의 상한이다.

둘째 줄에는 정수 $a_1, \ldots, a_n$ ($-10^{14} \le a_i \le 10^{14}$)이 주어진다.

곡의 최종 품질이 가질 수 있는 최댓값을 정수 하나로 출력한다.