Description

Lian-ge (pinyin) recently arrived in a magical kingdom where each citizen has either two subordinates or no subordinates, and these relations form a complete binary tree with $n$ levels. The subordinates of citizen $i$ are $2i$ and $2i +1$. The citizens on the lowest level, i.e., the leaves, are commoners and have no subordinates; the topmost citizen is the king, and those in between are nobles of various ranks.

A war has broken out in this kingdom. The king must decide whether each commoner should farm to supply food or join the war, and whether each noble (including the king) should manage logistics or lead troops in battle. A commoner contributes to all of their direct superiors. If a commoner $i$ joins the war and one of their direct superiors $j$ leads troops in battle, then the commoner’s combat contribution to that superior is $w_{ij}$. If a commoner $i$ farms and one of their direct superiors $j$ manages logistics, then the commoner’s logistics contribution to that superior is $f_{ij}$. If $i$ and $j$ engage in different affairs, then there is no contribution. To ensure logistics for the war, the king also requires that no more than $m$ commoners join the war.

The king wants to maximize the total contribution received by all nobles in the kingdom and has assigned this task to Lian-ge. Unfortunately, Lian-ge has many deadlines left unfinished and has passed this task on to you. Can you arrange it?

Input Format

The first line contains two numbers $n, m$.

The next $2^{n-1}$ lines each contain $n-1$ numbers. The $i$-th of these lines gives the combat contributions from the commoner numbered $2^{n-1}-1+ i$ to their $n-1$ direct superiors. The first number is the combat contribution $w_{ij}$ to their first-level direct superior, i.e., the noble numbered $\frac{2^{n-1}-1+ i}{2}$, and so on up the chain.

The next $2^{n-1}$ lines each contain $n-1$ numbers. The $i$-th of these lines gives the logistics contributions from the commoner numbered $2^{n-1}-1+ i$ to their $n-1$ direct superiors. The first number is the logistics contribution $f_{ij}$ to their first-level direct superior, i.e., the noble numbered $\frac{2^{n-1}-1+ i}{2}$, and so on up the chain.

Output Format

Output a single number: the maximum total contribution that satisfies the constraints.

3 4
503 1082
1271 369
303 1135
749 1289
100 54
837 826
947 699
216 389

6701

Hint

For $100 \%$ of the testdata, $2 \leq n \leq 10, \ m \leq 2^{n-1}, \ 0 \leq w_{ij}, f_{ij} \leq 2000$.

Translated by ChatGPT 5