OIG III - dom

// https://szkopul.edu.pl/problemset/problem/LdXEESx2SJmtrU_CkvAXwXNh/site/?key=statement
// OIG III (2 etap)

#include <iostream>
#include <math.h>

constexpr int sizik = 132072;

int v[sizik];
int dp[sizik][21];

int pot2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072};

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, k;
    std::cin >> n >> k;

    // k >>= 1;
    k /= 2;

    int curr = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << i); j++) {
            int a, b;
            std::cin >> a >> b;

            v[++curr] = a + b;
        }
    }

    for (int x = curr; x >= 1; x--) {
        dp[x][1] = v[x];

        for (int i = 2; i <= k; i++) {
            dp[x][i] = dp[x][i - 1];

            if (2 * x + 1 >= 131072) {
                continue;
            }

            for (int j = 0; j <= i - 1; j++) {
                dp[x][i] = std::max( //
                    dp[2 * x][j] + dp[2 * x + 1][i - 1 - j] + dp[x][1], //
                    dp[x][i] //
                );
            }
        }
    }

    std::cout << std::max(dp[1][k], 0) << '\n';

    return 0;
}