#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template <typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using si = set<int>;
using sl = set<ll>;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vi a, b;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if ((int)a.size() < n / 2) {
      a.push_back(x);
    } else {
      b.push_back(x);
    }
  }
  vi sums;
  for (int i = 0; i < (1 << (int)a.size()); ++i) {
    int sum = 0;
    for (int j = 0; j < (int)a.size(); ++j) {
      if ((i >> j) & 1) {
        sum += a[j];
        sum %= m;
      }
    }
    sums.push_back(sum);
  }
  sort((sums).begin(), (sums).end());
  int res = -1e9;
  for (int i = 0; i < (1 << (int)b.size()); ++i) {
    int sum = 0;
    for (int j = 0; j < (int)b.size(); ++j) {
      if ((i >> j) & 1) {
        sum += b[j];
        sum %= m;
      }
    }
    int want = m - sum - 1;
    res = max(res, (sum + sums[0]) % m);
    int it = upper_bound((sums).begin(), (sums).end(), want) - sums.begin();
    --it;
    if (it) {
      res = max(res, (sum + sums[it]) % m);
    }
  }
  cout << res << "\n";
  return 0;
}
