• Subtask 1: Duyệt mọi tập hợp các tem sao cho số loại tem còn lại là lớn nhất và tổng giá trị đổi con tem là ít nhất.

• Subtask 2: Nhận xét rằng số lượng loại tem tối đa có thể có là khoảng ~\sqrt{P}~, áp dụng quy hoạch động cái túi với ~dp[i][j]~ là số lượng tem ít nhất sử dụng khi xét tới tem thứ ~i~ và có tổng giá trị là ~j~. Độ phức tạp là ~O(P \times \sqrt{P})~

• Subtask 3: Cũng là quy hoạch động cái túi, với mỗi tem loại ~i~ xét từng trường hợp sử dụng tem, từ ~1~ đến ~cnt[i]~ là số lượng tem có thể sử dụng. Chỉ khi xài hết tem thì mới tăng ~1~ giá trị, còn lại thì không tăng. Lưu một mảng ~pre[i][j]~ là giá trị truy vết để biết coi tem thứ ~i~ được xài bao nhiêu lần. Độ phức tạp là ~O(N \times P)~

• Subtask 4: Khéo léo sử dụng CTDL, hoặc mảng queue/dequeue để loại bỏ vòng ~for~ cho việc duyệt số lượng sử dụng tem. Nhờ vậy, mỗi loại tem chỉ duyệt qua ~2 * P~ tổng giá trị knapsack, nên là có độ phức tạp quay trở lại ~O(P \times \sqrt{P})~

  Một tối ưu quan trọng là duy trì knapsack theo đúng kích thước tổng giá trị tem mà ta đang duyệt, nghĩa là xét tới tem bao nhiêu thì thêm vào kích thước cần xét bấy nhiêu.

#include <bits/stdc++.h>

using namespace std;

namespace std {
#ifndef LOCAL
#define cerr \
  if (0) cerr
#endif
}  // namespace std

const int N = 6e4 + 5;

int cnt[2 * N];
vector<bool> trace[N];
vector<uint16_t> dp[N];

bool minimize(uint16_t& a, uint16_t b) {
  if (a > b) return a = b, 1;
  return 0;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task "EXCHANGE"
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, p;
  cin >> n >> p;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    ++cnt[x];
  }
  vector<array<int, 3>> items = {{0, 0, 0}};
  int distinct = 0;
  int all = 0;
  for (int i = 0; i <= 2 * p; i++) {
    if (cnt[i]) {
      distinct++;
      int have = cnt[i];
      cnt[i]--;
      for (int j = 0; (1 << j) <= cnt[i]; ++j) {
        cnt[i] -= (1 << j);
        items.push_back({(1 << j) * i, 0, (1 << j)});
      }
      if (cnt[i] > 0) {
        items.push_back({cnt[i] * i, 0, cnt[i]});
      }
      items.push_back({i * have, 1, have});
      all += i * have;
    }
  }
  n = items.size() - 1;
  int pref = 0;
  for (int i = 0; i <= n; i++) {
    pref += items[i][0];
    dp[i].assign(pref + 1, 65000);
    trace[i].resize(pref + 1);
  }
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    int j = i;
    while (j <= n && items[j][1] != 1) ++j;
    for (int k = i; k < j; k++) {
      auto [w, v, c] = items[k];
      // j - w < dp[k-1].size()
      // j < dp[k-1].size() + w
      int max_w = min<int>(dp[k].size() - 1, dp[k - 1].size() + w - 1);
      for (int tot = 0; tot < dp[k - 1].size(); tot++) {
        dp[k][tot] = dp[k - 1][tot];
        trace[k][tot] = 0;
      }
      for (int tot = max_w; tot >= w; tot--) {
        if (minimize(dp[k][tot], dp[k - 1][tot - w])) {
          trace[k][tot] = 1;
        }
      }
    }
    auto [w, v, c] = items[j];
    int max_w = min<int>(dp[j].size() - 1, dp[i - 1].size() + w - 1);
    for (int k = 0; k < dp[j - 1].size(); k++) {
      dp[j][k] = dp[j - 1][k];
      trace[j][k] = 0;
    }
    for (int tot = max_w; tot >= w; tot--) {
      if (minimize(dp[j][tot], dp[i - 1][tot - w] + 1)) {
        trace[j][tot] = 1;
      }
    }
    i = j;
  }
  pair<uint16_t, int> best = {65000, -1};
  for (int j = p; j < dp[n].size(); ++j) {
    best = min(best, {dp[n][j], j});
  }
  cout << distinct - best.first << " " << best.second << '\n';
  int i = n, j = best.second;
  vector<int> used;
  while (i && j) {
    auto pick = trace[i][j];
    auto [w, v, c] = items[i];
    if (!pick) {
      i--;
      continue;
    }
    for (int sus = 0; sus < c; sus++) {
      used.emplace_back(w / c);
      j -= w / c;
    }
    if (v == 0) {
      i--;
    } else {
      i--;
      while (i >= 1 && items[i][1] != 1) i--;
    }
  }
  sort(used.begin(), used.end());
  for (auto it : used) cout << it << ' ';
  return 0;
}