#include <bits/stdc++.h>
const int N = 40, K = 19;
int n, m, k, ans, totx, toty;
long long a[N], x[1 << K], y[1 << K];
template <typename T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
void dfsx(int i, long long sum) {
  if (i > k) {
    x[++totx] = sum % m;
    return;
  }
  dfsx(i + 1, sum + a[i]);
  dfsx(i + 1, sum);
}
void dfsy(int i, long long sum) {
  if (i > n) {
    y[++toty] = sum % m;
    return;
  }
  dfsy(i + 1, sum + a[i]);
  dfsy(i + 1, sum);
}
int main() {
  read(n), read(m), k = n >> 1;
  for (int i = 1; i <= n; ++i) read(a[i]);
  dfsx(1, 0), dfsy(k + 1, 0);
  std::sort(&x[1], &x[totx + 1]);
  std::sort(&y[1], &y[toty + 1]);
  int l = 1, r = toty;
  while (l <= totx) {
    while (r && x[l] + y[r] >= m) --r;
    if (!r) break;
    ans = std::max(ans, int((x[l] + y[r]) % m)), ++l;
  }
  printf("%d\n", ans);
  return 0;
}
