#include <bits/stdc++.h>
using namespace std;
long long n, m, w[40], p[1 << 20], q[1 << 20], ans;
long long cntp, cntq, a[40], b[40];
void dfs1() {
  long long num = (n + 1) / 2;
  for (long long i = 0; i < num; i++) a[i] = w[i * 2 + 1];
  long long tot = (1 << num) - 1;
  for (long long i = 1; i <= tot; i++) {
    long long Tot = 0;
    for (long long j = 0; j < num; j++)
      if ((1 << j) & i) Tot += a[j], Tot %= m;
    p[++cntp] = Tot;
  }
}
void dfs2() {
  long long num = n / 2;
  for (long long i = 0; i < num; i++) b[i] = w[(i + 1) * 2];
  long long tot = (1 << num) - 1;
  for (long long i = 1; i <= tot; i++) {
    long long Tot = 0;
    for (long long j = 0; j < num; j++)
      if ((1 << j) & i) Tot += b[j], Tot %= m;
    q[++cntq] = Tot;
  }
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; i++) scanf("%lld", &w[i]);
  sort(w + 1, w + n + 1);
  dfs1();
  dfs2();
  sort(p + 1, p + cntp + 1);
  sort(q + 1, q + cntq + 1);
  int i = 0, j = cntq;
  while (i <= cntp) {
    while (p[i] + q[j] >= m) --j;
    ans = max(ans, p[i] + q[j]), ++i;
  }
  ans = max(ans, (p[cntp] + q[cntq]) % m);
  cout << ans << endl;
}
