#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
long long min(long long a, long long b) { return (a < b) ? a : b; }
long long max(long long a, long long b) { return (a > b) ? a : b; }
long long fp(long long a, long long b) {
  if (b == 0) return 1;
  long long x = fp(a, b / 2);
  x = (x * x) % mod;
  if (b & 1) x = (x * a) % mod;
  return x;
}
const long long N = 2e5 + 5;
vector<long long> v;
long long m, n;
long long a[N];
void solve(long long l, long long r, long long x, long long ok) {
  if (l > r) {
    if (ok) v.push_back(x % m);
    return;
  }
  solve(l + 1, r, x, ok);
  solve(l + 1, r, x + a[l], 1);
}
void solve() {
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  solve(1, n / 2, 0, 0);
  auto v1 = v;
  v.clear();
  solve(n / 2 + 1, n, 0, 0);
  auto v2 = v;
  sort(v1.begin(), v1.end());
  long long ans = 0;
  for (auto i : v1) ans = max(ans, i);
  for (auto i : v2) {
    ans = max(ans, i);
    long long l = 0;
    long long r = (long long)v1.size() - 1;
    long long tar = m - 1 - i;
    while (l <= r) {
      long long mid = (l + r) / 2;
      if (v1[mid] <= tar) {
        ans = max(ans, v1[mid] + i);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  srand(time(0));
  long long t = 1;
  for (long long i = 1; i <= t; i++) {
    solve();
  }
}
