House of Cards

Time limit1sMemory limit512 MB

Summary

Marcel removes at most k cards in whole leaning pairs, clearing cards above before the cards they rest on, to maximize the recovered sum.

Level: Hard8 of 10
Topics: Dynamic programming, Tree
Solved: No attempts yet

Problem

Marcel received a very special deck of cards for his birthday this year. They are not for playing games but for building houses (towers) of cards. As soon as he unwrapped the gift, Marcel built a huge tower. He did it like this: first he leaned two cards against each other to form one peak, then on the peaks he had made he leaned two more cards against each other, and so on, building each higher floor on top of the peaks below. On every floor except the bottom one the number of peaks was always even, so it was always possible to build the next floor correctly.

Every card has its own value. Marcel now regrets that he did not plan his tower more carefully and used too many valuable cards. Knowing the value of every card, he wants to take at most $k$ cards out of the tower so that the sum of their values is as large as possible. Of course, the house of cards must not collapse in the process.

For the house to stay stable after the cards are removed, Marcel must obey two rules. First, the two cards of a pair that lean against and support each other must always be removed together; he can never take out just one of them. Second, before he can remove a card, he must first remove every card that lies above it and rests on it, directly or indirectly.

Input

The first line contains two integers $n$ and $k$ ( $2 \le n \le 17$ , $2 \le k \le 40$ ): the number of floors of the card tower and the maximum number of cards Marcel may remove. Because cards can only be removed in pairs, $k$ is always even.

The next $n$ lines describe the floors of the tower from the top down. The line for the $i$ -th floor from the top ( $1 \le i \le n$ ) contains $2^i$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,2^i}$ , the values of the cards on that floor listed from left to right ( $-1\,000\,000 \le a_{i,j} \le 1\,000\,000$ ).

Output

Print a single integer: the maximum total value of cards Marcel can recover by removing at most $k$ cards without letting the tower collapse.

Hint

The cards Marcel should take out are marked with dashed lines in the figure. Their values are $1$ , $-3$ , $2$ , $1$ , $-1$ , $5$ , so the sum of their values is $5$ .

Examples5

Example 1
Input
```
3 6
1 -3
-10 1 2 1
1 1 3 2 -1 5 2 -3
```
Expected output
```
5
```
Example 2
Input
```
2 2
3 4
1 2 3 4
```
Expected output
```
7
```
Example 3
Input
```
2 2
-3 -4
1 2 3 4
```
Expected output
```
0
```
Example 4
Input
```
2 4
-5 -5
8 9 -100 -100
```
Expected output
```
7
```
Example 5
Input
```
2 4
-1 -2
-3 -4 -5 -6
```
Expected output
```
0
```