У Валеры имеется массив a, состоящий из n целых чисел a0, a1, ..., an - 1, и функция f(x) принимающая в качестве своего единственного аргумента целое число от 0 до 2n - 1. Значение f(x) считается по формуле 
, где значение bit(i) равно единице, если в двоичном представлении числа x в i-ой позиции стоит 1, или нулю в противном случае.
Например, если n = 4, а x = 11 (11 = 20 + 21 + 23), тогда f(x) = a0 + a1 + a3.
Помогите Валере найти максимум функции f(x) среди всех x, для которых выполняется неравенство: 0 ≤ x ≤ m.
Выходные данные
Выведите единственное целое число — максимальное значение функции f(x) среди всех 
.
Примечание
В первом тестовом примере m = 20 = 1, f(0) = 0, f(1) = a0 = 3.
Во втором примере m = 20 + 21 + 23 = 11, а максимальное значение функции равно f(5) = a0 + a2 = 17 + 10 = 27.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 8
10
|
3
|
|
2
|
5
17 0 10 2 1
11010
|
27
|