McApp

Cerință

Se dau $k$, o matrice $mat$ de dimensiuni $k \times k$ și un $x$. Definim $f(cnt, n)$, unde $cnt$ și $n$ sunt numere naturale astfel:

• Dacă $n=0, f(cnt, n)=0$;
• Altfel, se va considera $lsb$-ul lui $n$. Fie acesta $b$. Atunci, $f(cnt, n)=mat_{(cnt, b)} \cdot cnt + f(cnt+1, n-2^b)$.

Numim $lsb$-ul unui număr natural $x$ astfel:

• Numărul natural minim $b$, $b \geq 0$, astfel încât $2^b \mid n$, iar $2^{b+1} \nmid n$

Să se afișeze $f(0, i)$ maxim, pentru $0 \leq i \leq x$.

Atenție! Pentru că $x$ nu încape într-un long long și nici într-un __int128, ți se oferă direct reprezentarea lui în baza 2, sub forma unui șir de exact $k$ cifre binare (se garantează că $x$ are cel mult $k$ cifre în această reprezentare). De asemenea, prima cifră ar putea fi 0 (dacă $x$ are $k-1$ sau mai puține cifre în baza $2$).

Date de intrare

Pe prima linie se găsește un numar întreg, $k$. Pe a doua linie se va găsi reprezentarea lui $x$ în baza $2$. Pe urmatoarele $k$ linii se vor afla cate $k$ valori, a $j + 1$-a valoare de pe a $i + 1$-a linie reprezentând $mat_{(i, j)}$, pentru oricare $0 \leq i, j <k$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, maximul valorilor $f(0, i), 0 \leq i \leq x$.

Restricții și precizări

• $1 \leq k \leq 2 \ 000$;
• $0 \leq x < 2^k$;
• Se garantează faptul că reprezentarea în baza $2$ a lui $x$ dată are exact $k$ biți;
• $1 \leq mat_{(i, j)} \leq 10^9$, pentru oricare $0 \leq i, j < k$;

Exemplul 1

stdin

3
111
1 1 1
1 7 10
1 9 11

stdout

29

Explicație

Tabelul valorilor $f(0, i), 0 \leq i \leq 7$ este:

• $f(0, 0)=0$
• $f(0, 1)=0$
• $f(0, 2)=0$
• $f(0, 3)=7$
• $f(0, 4)=0$
• $f(0, 5)=10$
• $f(0, 6)=10$
• $f(0, 7)=29$

Maximul dintre acestea este $29$.

Exemplul 2

stdin

3
101
1 1 1
1 7 10
1 9 11

stdout

10

Explicație

Tabelul valorilor $f(0, i), 0 \leq i \leq 7$ este cel de mai sus. Maximul valorilor pentru $0 \leq i \leq 5$ este $10$.

Exemplul 3

stdin

6
001101
1014 199 19 919 6584 1812
1823 129 22 43949 49404 1088
19383347 489747 4918 43893 340893 3498
19877 39390 5759 345678 4747 3264
144 74 44410 14 7989 1089
441 94 141 41 9 898911

stdout

87915

Explicație

Te descurci singur, sper...