#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
const long long inf = 1ll << 60;
const long long iinf = 2147483647;
const long long mod = 998244353;
const long long maxn = 1e3 + 5;
long long pw(long long x, long long p) {
  long long ret = 1;
  while (p > 0) {
    if (p & 1) {
      ret *= x;
      ret %= mod;
    }
    x *= x;
    x %= mod;
    p >>= 1;
  }
  return ret;
}
long long inv(long long x) { return pw(x, mod - 2); }
long long n, m;
vector<long long> vc, posa, posb;
void reca(long long x, long long sum) {
  posa.push_back(0);
  for (long long i = (0); i < (n / 2); i++) {
    long long second = (long long)(posa.size());
    for (long long j = (0); j < (second); j++) {
      posa.push_back((posa[j] + vc[i]) % m);
    }
  }
}
void recb(long long x, long long sum) {
  posb.push_back(0);
  for (long long i = (n / 2); i < (n); i++) {
    long long second = (long long)(posb.size());
    for (long long j = (0); j < (second); j++) {
      posb.push_back((posb[j] + vc[i]) % m);
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  cin >> n >> m;
  vc.resize(n);
  for (long long i = (0); i < (n); i++) {
    cin >> vc[i];
    vc[i] %= m;
  }
  reca(0, 0);
  sort(posa.begin(), posa.end(), greater<long long>());
  posa.resize(unique(posa.begin(), posa.end()) - posa.begin());
  recb(n / 2, 0);
  sort(posb.begin(), posb.end());
  posb.resize(unique(posb.begin(), posb.end()) - posb.begin());
  long long r = 0, ans = vc[0];
  long long ma = (long long)(posa.size()), mb = (long long)(posb.size());
  for (long long i = (0); i < (ma); i++) {
    while (r + 1 < mb && (posa[i] + posb[r + 1]) < m) {
      r++;
    }
    ans = max(ans, (posa[i] + posb[r]) % m);
  }
  cout << ans << '\n';
}
