#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long num = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    num = num * 10 + c - '0';
    c = getchar();
  }
  return num * f;
}
long long n, m, a[45], ans = 0;
set<long long> s, t;
void dfs(int cur, long long sum) {
  if (cur == n / 2 + 1) {
    sum = sum % m;
    s.insert(sum);
    return;
  }
  dfs(cur + 1, sum);
  dfs(cur + 1, sum + a[cur]);
}
void dfs2(int cur, long long sum) {
  if (cur == n + 1) {
    sum = sum % m;
    t.insert(sum);
    return;
  }
  dfs2(cur + 1, sum);
  dfs2(cur + 1, sum + a[cur]);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  dfs(1, 0);
  dfs2(n / 2 + 1, 0);
  for (set<long long>::iterator it = s.begin(); it != s.end(); ++it) {
    long long tmp = *it;
    set<long long>::iterator pos = t.lower_bound(m - tmp);
    if (pos != t.begin()) {
      --pos;
      if (*pos + tmp <= m) ans = max(ans, *pos + tmp);
    }
  }
  printf("%I64d", ans);
  return 0;
}
