26661번 - Muzyka pop 다국어

Mateusz uwielbia muzykę pop. Jest odprężająca, świetnie się do niej tańczy, a nawet pomaga w programowaniu. Te wszystkie zalety wymagają jednak dobrego zgrania melodii z bitem.

Mateusz stworzył właśnie nową melodię i zamierza dopasować do niej dobre bity. Melodia trwa n sekund i niektóre jej momenty mogą być dużo lepsze od innych. Jakość i-tej sekundy melodii jest opisana liczbą całkowitą a_i (być może ujemną) i trzeba do niej dobrać nieujemny całkowity współczynnik bitowego wzmocnienia b_i. Współczynnik wzmacnia tę sekundę C(b_i)-krotnie, gdzie C(b_i) oznacza liczbę zapalonych bitów w zapisie binarnym liczby b_i.^∗ Przykładowo, wybranie b_i = 13 daje trzykrotne wzmocnienie i-tej sekundy melodii, gdyż zapisem binarnym liczby 13 jest 1101 i zawiera on trzy zapalone bity.

Ostateczną jakość całej piosenki możemy zapisać jako:

a₁ · C(b₁) + a₂ · C(b₂) + . . . + a_n · C(b_n).

Każdy lubi piosenki z narastającym wzmocnieniem bitowym i Mateusz nie jest wyjątkiem. Współczynniki bitowe b_i muszą tworzyć rosnący ciąg nieujemnych liczb całkowitych z pewnym górnym limitem m:

0 ≤ b₁ < b₂ < . . . < b_n ≤ m.

Celem Mateusza jest takie dobranie współczynników bitowych, aby zmaksymalizować ostateczną jakość piosenki. Jaką największą wartość może on otrzymać?

^∗Innymi słowy, C(b_i) jest liczbą jedynek w zapisie binarnym liczby b_i.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n, m (1 ≤ n ≤ 200, n − 1 ≤ m ≤ 10¹⁸), oznaczające długość trwania piosenki w sekundach oraz górne ograniczenie na współczynniki bitowe.

W drugim wierszu wejścia znajduje się n liczb całkowitych a₁, . . . , a_n (−10¹⁴ ≤ a_i ≤ 10¹⁴), oznaczających jakości kolejnych sekund melodii.

Na wyjściu powinna znajdować się jedna liczba całkowita – maksymalna możliwa ostateczna jakość piosenki.

Wyjaśnienie pierwszego przykładu: Melodia składa się z trzech sekund o jakościach odpowiednio 2, −1, 3. Zauważ, że jakość sekundy może być ujemna! Optymalnym ciągiem b jest b₁ = 3, b₂ = 4, b₃ = 5. Wtedy otrzymujemy:

a₁ · C(b₁) + a₂ · C(b₂) + a₃ · C(b₃) = 2 · C(3) + (−1) · C(4) + 3 · C(5) = 2 · 2 + (−1) · 1 + 3 · 2 = 9