Вам дано масив a, що складається з n цілих чисел і ціле число m.
Виберіть послідовність позицій b[1]
, b[2]
, ..., b[k]
(1 ≤ b[1]
<b2 <... < b[k]
≤ n) таку, щоб значення було максимальне. Обрана підпослідовність може бути порожньою.
Підрахуйте максимальне можливе значення.
У першому рядку записані два цілих числа n і m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10^9
).
У другому рядку записані n цілих чисел a[1], a[2], ..., a[n]
(1 ≤ a[i]
≤ 10^9
).
Виведіть максимальне можливе значення.