#include <bits/stdc++.h>
using namespace std;
const long long mx = 105;
const long long mod = 998244353;
const long long maxn = 1e17;
void solve() {
  long long n, m, i, j, k;
  cin >> n >> m;
  long long a[n];
  for (i = 0; i < n; i++) {
    cin >> a[i];
    a[i] %= m;
  }
  set<long long> sa, sb;
  long long e = n / 2 - 1;
  for (i = 0; i <= pow(2, n / 2) - 1; i++) {
    long long te = i;
    long long cur = 0, s = 0;
    while (te > 0) {
      if (te % 2 == 1) {
        s += a[cur];
      }
      cur++;
      te /= 2;
    }
    sa.insert(s % m);
  }
  for (i = 0; i <= pow(2, n - n / 2) - 1; i++) {
    long long te = i;
    long long cur = 0, s = 0;
    while (te > 0) {
      if (te % 2 == 1) {
        s += a[cur + n / 2];
      }
      cur++;
      te /= 2;
    }
    sb.insert(s % m);
  }
  long long res = 0;
  vector<long long> va, vb;
  for (auto it : sb) {
    vb.push_back(it);
  }
  for (auto it : sa) {
    va.push_back(it);
  }
  for (i = 0; i < (int)vb.size(); i++) {
    long long val = vb[i], tf = m - val - 1;
    long long l = 0, h = (int)va.size() - 1, mi, cur = -1;
    while (l <= h) {
      mi = l + (h - l) / 2;
      if (va[mi] <= tf) {
        cur = va[mi];
        l = mi + 1;
      } else {
        h = mi - 1;
      }
    }
    if (cur != -1) {
      res = max(res, cur + val);
    }
    res = max(res, (val + va[(int)va.size() - 1]) % m);
  }
  cout << res << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
}
