#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[50];
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int sz1 = n / 2, sz2 = (n + 1) / 2;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<ll> s1;
  s1.push_back(0);
  for (int i = 0; i < (1 << sz1); ++i) {
    ll s = 0;
    for (int j = 0; j < sz1; ++j) {
      if (i & (1 << j)) s = (s + a[j]) % m;
    }
    s1.push_back(s);
  }
  vector<ll> s2;
  s2.push_back(0);
  for (int i = 0; i < (1 << sz2); ++i) {
    ll s = 0;
    for (int j = 0; j < sz2; ++j) {
      if (i & (1 << j)) s = (s + a[sz1 + j]) % m;
    }
    s2.push_back(s);
  }
  sort(s1.begin(), s1.end());
  sort(s2.begin(), s2.end());
  ll ans = 0;
  for (ll x : s1) {
    auto it = lower_bound(s2.begin(), s2.end(), m - x - 1);
    if (it == s2.end() || (it != s2.begin() && *it > (m - x - 1))) --it;
    ans = max(ans, (x + (*it)) % m);
  }
  cout << ans << endl;
  return 0;
}
