C. Хамгийн их утгыг ол

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валерад $0$-ээс $2^n-1$ хүртэлх бүхэл тоонуудаас аргументээ авах $f(x)$ функц болон $n$ бүхэл тоо бүхий $a_0, a_1, ... , a_{n - 1}$ массив байв.$x$-ийн хоёртын бичиглэлд $i$ дугаар байранд дахь утгыг илэрхийлэх $bit(i)$ функцээр тэмдэглэвэл томъёогоор f(x)-ийн утгыг бодно.

Жишээлбэл хэрвээ $n = 4$ ба $x = 11$ ($11 = 2^0 + 2^1 + 2^3$) байвал $f(x) = a_0 + a_1 + a_3$ байна.

Валерад $x$ ($0 ≤ x ≤ m$) байх $f(x)$ функцийн хамгийн их утгыг олоход нь туслаарай.

Оролт

Эхний мөр массивийн элементийн $n$ ($1 ≤ n ≤ 10^5$) бүхэл тоог агуулна. Дараагийн мөрөнд $а$ массив $a_0, a_1, ... , a_{n-1}$ ($0 ≤ a_i ≤ 10^4$) болох $n$ тоо зайгаар тусгаарлагдан өгөгдөнө.

Гуравдугаар мөрөнд $m$ тооны хоёртын илэрхийлэл $s_0 s_1 ... s_{n-1}$ дараалал өгөгдөнө. $m$ тоо нь -тэй тэнцүү.

Гаралт

Бүх дэх $f(x)$ функцийн хамгийн их утга болох нэг бүхэл тоог хэвлэнэ.

Орчуулсан: Батхишиг

Жишээ тэстүүд

Оролт
2
3 8
10
Гаралт
3
Оролт
5
17 0 10 2 1
11010
Гаралт
27

Тэмдэглэл

In the first test case $m = 2^{0} = 1, f(0) = 0, f(1) = a_{0} = 3$.

In the second sample $m = 2^{0} + 2^{1} + 2^{3} = 11$, the maximum value of function equals $f(5) = a_{0} + a_{2} = 17 + 10 = 27$.

Сэтгэгдлүүдийг ачааллаж байна...