Kingdom War and Logistics Assignment

In a magical kingdom, every citizen is arranged in a complete binary tree with n levels. Citizen 1 is the king (root), and every non‐leaf node (noble) has exactly two subordinates: if a citizen is numbered i then its two subordinates are 2i and 2i+1. The citizens on the bottom level (leaves) are commoners. A war has broken out, and the king must assign roles as follows:

• Each commoner (leaf) is either sent to fight in the war or ordered to farm to supply food.
• Each noble (including the king) chooses either to lead troops in battle or to manage logistics.

For each commoner i and each of his direct ancestors (i.e. all nobles on the unique path from the commoner to the king), a contribution is generated depending on their respective choices. Specifically, let the level of a node be defined as follows: the king is on level 1 and the leaves are on level n. If a commoner i (leaf) is at level n and one of his ancestors j is at level L (so the distance is d=n-L), then:

• If commoner i goes to war and noble j leads troops, the contribution is \(w_{ij}=w_i[d]\) (note that the input gives the war contributions as a list of \(n-1\) numbers for each leaf, with \(w_i[0]\) corresponding to the immediate parent, \(w_i[1]\) to the grandparent, etc.).
• If commoner i farms and noble j manages logistics, the contribution is \(f_{ij}=f_i[d]\) (with a similar indexing convention: \(f_i[0]\) for the immediate parent, etc.).
• If their choices do not match (i.e. one participates in war and the other does not), the contribution is zero.

The twist is that, to preserve the kingdom’s food supply, at most m commoners are allowed to go to war. Each noble (who does not have a predetermined contribution mechanism) will choose the option (either war or logistics) that yields the higher total contribution from all commoners in his subtree. That is, for each noble j, if the commoners in his subtree who have chosen war would contribute a total of \(S_w(j)\) (using the appropriate \(w\) values) and those who farm would contribute \(S_f(j)\) (using the \(f\) values), then noble j gains a contribution of

[ \max\bigl(S_w(j),; S_f(j)\bigr). ]

Your task is to decide the roles for all commoners (leaves) (subject to at most m commoners going to war) so that the sum of contributions over all nobles (internal nodes) is maximized.

Input and output formats are described below.

inputFormat

The input is given as follows:

1. The first line contains two integers n and m (2 ≤ n ≤ (small number) and 0 ≤ m ≤ 2^(n-1)), where n is the number of levels in the complete binary tree and m is the maximum number of commoners (leaves) allowed to go to war.
2. The next \(2^{n-1}\) lines each contain \(n-1\) integers. The \(i\)th of these lines corresponds to a leaf (in increasing order of their indices from \(2^{n-1}\) to \(2^n-1\)) and lists the war contributions \(w_i[0], w_i[1], \ldots, w_i[n-2]\). Here, \(w_i[0]\) is the contribution if the leaf works with its immediate parent (distance 1), \(w_i[1]\) with its grandparent (distance 2), etc.
3. The next \(2^{n-1}\) lines each contain \(n-1\) integers. Similarly, the \(i\)th of these lines corresponds to the same leaf and lists the farming contributions \(f_i[0], f_i[1], \ldots, f_i[n-2]\), with the same ordering convention.

You may assume that all the contribution values are nonnegative integers.

outputFormat

Output a single integer: the maximum total contribution that can be obtained by optimally assigning roles to all commoners and having each noble choose the option that maximizes his own contribution.

Note: The total contribution is calculated as the sum over all nobles (internal nodes) of \(\max(S_w(j), S_f(j))\), where the sums are taken over all commoners in the noble's subtree.

sample

3 1
1 2
0 3
2 2
1 1
2 1
1 1
0 4
1 1
3 2

6

</p>