description: There are currently n hot topics numbered from 0 to n-1 at your local bridge club and 2^n players numbered from 0 to 2^n-1. Each player holds a different set of views on those n topics, more specifically, the i-th player holds a positive view on the j-th topic if i\ \&\ 2^j > 0, and a negative view otherwise. Here \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).
  
  You are going to organize a bridge tournament capable of accommodating at most k pairs of players (bridge is played in teams of two people). You can select teams arbitrarily while each player is in at most one team, but there is one catch: two players cannot be in the same pair if they disagree on 2 or more of those n topics, as they would argue too much during the play.
  
  You know that the i-th player will pay you a_i dollars if they play in this tournament. Compute the maximum amount of money that you can earn if you pair the players in your club optimally.
  
  Input
  
  The first line contains two integers n, k (1 ≤ n ≤ 20, 1 ≤ k ≤ 200) — the number of hot topics and the number of pairs of players that your tournament can accommodate.
  
  The second line contains 2^n integers a_0, a_1, ..., a_{2^n-1} (0 ≤ a_i ≤ 10^6) — the amounts of money that the players will pay to play in the tournament.
  
  Output
  
  Print one integer: the maximum amount of money that you can earn if you pair the players in your club optimally under the above conditions.
  
  Examples
  
  Input
  
  
  3 1
  8 3 5 7 1 10 3 2
  
  
  Output
  
  
  13
  
  
  Input
  
  
  2 3
  7 4 5 7
  
  
  Output
  
  
  23
  
  
  Input
  
  
  3 2
  1 9 1 5 7 8 1 1
  
  
  Output
  
  
  29
  
  Note
  
  In the first example, the best we can do is to pair together the 0-th player and the 2-nd player resulting in earnings of 8 + 5 = 13 dollars. Although pairing the 0-th player with the 5-th player would give us 8 + 10 = 18 dollars, we cannot do this because those two players disagree on 2 of the 3 hot topics.
  
  In the second example, we can pair the 0-th player with the 1-st player and pair the 2-nd player with the 3-rd player resulting in earnings of 7 + 4 + 5 + 7 = 23 dollars.
solution: #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  using vvi = vector<vector<int>>;
  using vi = vector<int>;
  using vvll = vector<vector<long long>>;
  using vll = vector<long long>;
  using vd = vector<double>;
  using vvd = vector<vector<double>>;
  using pii = pair<int, int>;
  using vpii = vector<pair<int, int>>;
  template <typename C>
  struct rge {
    C l, r;
  };
  template <typename C>
  rge<C> range(C i, C j) {
    return rge<C>{i, j};
  }
  template <typename C>
  ostream& operator<<(ostream& os, rge<C>& r) {
    os << '{';
    for (auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it;
    os << '}';
    return os;
  }
  template <typename A, typename B>
  ostream& operator<<(ostream& os, const pair<A, B>& p) {
    return os << '{' << p.first << "," << p.second << '}';
  }
  template <typename T_container, typename T = typename enable_if<
                                      !is_same<T_container, string>::value,
                                      typename T_container::value_type>::type>
  ostream& operator<<(ostream& os, const T_container& v) {
    os << '{';
    string sep;
    for (const T& x : v) os << sep << x, sep = ",";
    return os << '}';
  }
  void dbg_out() { cerr << ']' << endl; }
  template <typename A>
  void dbg_out(A H) {
    cerr << H;
    dbg_out();
  }
  template <typename A, typename B, typename... C>
  void dbg_out(A H, B G, C... T) {
    cerr << H << ",";
    dbg_out(G, T...);
  }
  namespace atcoder {
  namespace internal {
  template <class T>
  struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
      payload.clear();
      pos = 0;
    }
    void pop() { pos++; }
  };
  }  // namespace internal
  }  // namespace atcoder
  namespace atcoder {
  namespace internal {
  template <class E>
  struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
      for (auto e : edges) {
        start[e.first + 1]++;
      }
      for (int i = 1; i <= n; i++) {
        start[i] += start[i - 1];
      }
      auto counter = start;
      for (auto e : edges) {
        elist[counter[e.first]++] = e.second;
      }
    }
  };
  }  // namespace internal
  }  // namespace atcoder
  namespace atcoder {
  template <class Cap, class Cost>
  struct mcf_graph {
   public:
    mcf_graph() {}
    explicit mcf_graph(int n) : _n(n) {}
    int add_edge(int from, int to, Cap cap, Cost cost) {
      assert(0 <= from && from < _n);
      assert(0 <= to && to < _n);
      assert(0 <= cap);
      assert(0 <= cost);
      int m = int(_edges.size());
      _edges.push_back({from, to, cap, 0, cost});
      return m;
    }
    struct edge {
      int from, to;
      Cap cap, flow;
      Cost cost;
    };
    edge get_edge(int i) {
      int m = int(_edges.size());
      assert(0 <= i && i < m);
      return _edges[i];
    }
    std::vector<edge> edges() { return _edges; }
    std::pair<Cap, Cost> flow(int s, int t) {
      return flow(s, t, std::numeric_limits<Cap>::max());
    }
    std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
      return slope(s, t, flow_limit).back();
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
      return slope(s, t, std::numeric_limits<Cap>::max());
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
      assert(0 <= s && s < _n);
      assert(0 <= t && t < _n);
      assert(s != t);
      int m = int(_edges.size());
      std::vector<int> edge_idx(m);
      auto g = [&]() {
        std::vector<int> degree(_n), redge_idx(m);
        std::vector<std::pair<int, _edge>> elist;
        elist.reserve(2 * m);
        for (int i = 0; i < m; i++) {
          auto e = _edges[i];
          edge_idx[i] = degree[e.from]++;
          redge_idx[i] = degree[e.to]++;
          elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}});
          elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}});
        }
        auto _g = internal::csr<_edge>(_n, elist);
        for (int i = 0; i < m; i++) {
          auto e = _edges[i];
          edge_idx[i] += _g.start[e.from];
          redge_idx[i] += _g.start[e.to];
          _g.elist[edge_idx[i]].rev = redge_idx[i];
          _g.elist[redge_idx[i]].rev = edge_idx[i];
        }
        return _g;
      }();
      auto result = slope(g, s, t, flow_limit);
      for (int i = 0; i < m; i++) {
        auto e = g.elist[edge_idx[i]];
        _edges[i].flow = _edges[i].cap - e.cap;
      }
      return result;
    }
  
   private:
    int _n;
    std::vector<edge> _edges;
    struct _edge {
      int to, rev;
      Cap cap;
      Cost cost;
    };
    std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g, int s, int t,
                                            Cap flow_limit) {
      std::vector<std::pair<Cost, Cost>> dual_dist(_n);
      std::vector<int> prev_e(_n);
      std::vector<bool> vis(_n);
      struct Q {
        Cost key;
        int to;
        bool operator<(Q r) const { return key > r.key; }
      };
      std::vector<int> que_min;
      std::vector<Q> que;
      auto dual_ref = [&]() {
        for (int i = 0; i < _n; i++) {
          dual_dist[i].second = std::numeric_limits<Cost>::max();
        }
        std::fill(vis.begin(), vis.end(), false);
        que_min.clear();
        que.clear();
        size_t heap_r = 0;
        dual_dist[s].second = 0;
        que_min.push_back(s);
        while (!que_min.empty() || !que.empty()) {
          int v;
          if (!que_min.empty()) {
            v = que_min.back();
            que_min.pop_back();
          } else {
            while (heap_r < que.size()) {
              heap_r++;
              std::push_heap(que.begin(), que.begin() + heap_r);
            }
            v = que.front().to;
            std::pop_heap(que.begin(), que.end());
            que.pop_back();
            heap_r--;
          }
          if (vis[v]) continue;
          vis[v] = true;
          if (v == t) break;
          Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
          for (int i = g.start[v]; i < g.start[v + 1]; i++) {
            auto e = g.elist[i];
            if (!e.cap) continue;
            Cost cost = e.cost - dual_dist[e.to].first + dual_v;
            if (dual_dist[e.to].second - dist_v > cost) {
              Cost dist_to = dist_v + cost;
              dual_dist[e.to].second = dist_to;
              prev_e[e.to] = e.rev;
              if (dist_to == dist_v) {
                que_min.push_back(e.to);
              } else {
                que.push_back(Q{dist_to, e.to});
              }
            }
          }
        }
        if (!vis[t]) {
          return false;
        }
        for (int v = 0; v < _n; v++) {
          if (!vis[v]) continue;
          dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
        }
        return true;
      };
      Cap flow = 0;
      Cost cost = 0, prev_cost_per_flow = -1;
      std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
      while (flow < flow_limit) {
        if (!dual_ref()) break;
        Cap c = flow_limit - flow;
        for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
          c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
        }
        for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
          auto& e = g.elist[prev_e[v]];
          e.cap += c;
          g.elist[e.rev].cap -= c;
        }
        Cost d = -dual_dist[s].first;
        flow += c;
        cost += c * d;
        if (prev_cost_per_flow == d) {
          result.pop_back();
        }
        result.push_back({flow, cost});
        prev_cost_per_flow = d;
      }
      return result;
    }
  };
  }  // namespace atcoder
  void solve() {
    int n, k;
    scanf("%d%d", &n, &k);
    vi v(1 << n);
    for (int i = 0; i < v.size(); i++) scanf("%d", &v[i]);
    vector<pair<int, pii>> edges;
    for (int i = 0; i < v.size(); i++) {
      for (int b = 0; b < n; b++) {
        if ((i >> b) & 1) {
          edges.push_back({-(v[i] + v[i ^ (1 << b)]), {i, i ^ (1 << b)}});
        }
      }
    };
    int limit = min((int)edges.size(), (k - 1) * (2 * n - 1) + 1);
    ;
    cerr << "lim" << endl;
    nth_element(edges.begin(), edges.begin() + limit - 1, edges.end());
    cerr << "nth" << endl;
    int s = (1 << n);
    int t = s + 1;
    atcoder::mcf_graph<int, ll> mcmf(t + 1);
    vi good(1 << n);
    for (int i = 0; i < limit; i++) {
      int nu = edges[i].second.first, nv = edges[i].second.second,
          w = edges[i].first;
      if (__builtin_popcount(nv) & 1) {
        swap(nu, nv);
      }
      good[nu] = 1;
      good[nv] = 1;
      mcmf.add_edge(nu, nv, 1, int(2e6) + w);
    }
    for (int i = 0; i < (1 << n); i++) {
      if (!good[i]) continue;
      if (__builtin_popcount(i) & 1) {
        mcmf.add_edge(s, i, 1, 0);
      } else {
        mcmf.add_edge(i, t, 1, 0);
      }
    }
    pair<int, ll> res = mcmf.flow(s, t, k);
    cout << 1LL * res.first * int(2e6) - res.second << endl;
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
  }
  