#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 40;
int n, m, a[maxn], n2;
int t[1000000], tot;
void dfs(int u, int s) {
  if (u > n2) {
    t[++tot] = s;
    return;
  }
  dfs(u + 1, s);
  dfs(u + 1, (s + a[u]) % m);
}
int mx = 0;
void dfs1(int u, int s) {
  if (u > n) {
    int idx = lower_bound(t + 1, t + tot + 1, m - s) - 1 - t;
    mx = max(mx, s + t[idx]);
    return;
  }
  dfs1(u + 1, s);
  dfs1(u + 1, (s + a[u]) % m);
}
inline void init() {
  n = read();
  m = read();
  for (int i = (1), _end_ = (n); i <= _end_; i++) a[i] = read();
  n2 = n >> 1;
  dfs(1, 0);
  sort(t + 1, t + tot + 1);
  dfs1(n2 + 1, 0);
  printf("%d\n", mx);
}
int main() {
  init();
  return 0;
}
