#include <bits/stdc++.h>
using namespace std;
long long A[40], mod, ans, tmp, t;
int n, m, x, y, z, k, w;
long long B[1100000], C[1100000];
set<long long> s;
set<long long>::iterator it;
void solve(int x, long long val, int top) {
  if (x == top) {
    if (top == n)
      B[w++] = val;
    else
      C[k++] = val;
  } else {
    solve(x + 1, (val + A[x]) % mod, top);
    solve(x + 1, val, top);
  }
}
int main() {
  scanf("%d %lld", &n, &mod);
  for (int i = (0); i < (n); i++) scanf("%lld", &A[i]);
  for (int i = (0); i < (n); i++) A[i] %= mod;
  if (n <= 20) {
    solve(0, 0, n);
    ans = 0;
    for (int i = (0); i < (w); i++)
      if (B[i] > ans) ans = B[i];
    printf("%lld\n", ans);
    return 0;
  }
  solve(0, 0, 20);
  solve(20, 0, n);
  for (int i = (0); i < (w); i++) s.insert(B[i]);
  for (int i = (0); i < (k); i++) {
    tmp = C[i];
    tmp = mod - C[i];
    if (*s.begin() < tmp) {
      it = --(s.lower_bound(tmp));
      t = (*it) + C[i];
      ans = max(ans, t);
    }
    tmp = *s.rbegin();
    t = (tmp + C[i]) % mod;
    ans = max(ans, t);
  }
  printf("%lld\n", ans);
  return 0;
}
