#include <bits/stdc++.h>
using namespace std;
const int N = 100001, M = 37;
long long q[N];
int v[M][N];
vector<long long> a;
vector<long long> b;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> q[i];
  int k = n / 2;
  int l = n - k;
  int B = (1 << k);
  for (int i = 0; i < B; i++) {
    long long ans = 0;
    for (int j = 0; j < k; j++)
      if ((i & (1 << j))) ans += q[j];
    ans %= m;
    a.push_back(ans);
  }
  sort(a.begin(), a.end());
  B = (1 << l);
  for (int i = 0; i < B; i++) {
    long long ans = 0;
    for (int j = 0; j < l; j++)
      if ((i & (1 << (j)))) ans += q[j + k];
    ans %= m;
    b.push_back(ans);
  }
  long long ans = (a.back() + b.back()) % m;
  sort(b.begin(), b.end());
  for (int i = 0; i < a.size(); i++) {
    int l = -1, r = b.size();
    while (r - l > 1) {
      int mid = (r + l) / 2;
      if (a[i] + b[mid] >= m)
        r = mid;
      else
        l = mid;
    }
    if (l != -1) ans = max(ans, b[l] + a[i]);
  }
  cout << ans;
  return 0;
}
