#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int MAX = 100005;
const int MOD = 1000000000 + 7;
const int nr[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int nc[] = {0, 0, 1, -1, 1, -1, 1, -1};
long long n, mx, x[37], m, cnt, cnt2, y[632000], z[963000];
void bf1(int idx, long long jlh) {
  if (idx > 17 || idx > n) return;
  cnt++;
  y[cnt] = (jlh + x[idx]) % m;
  bf1(idx + 1, (jlh + x[idx]) % m);
  bf1(idx + 1, jlh);
}
void bf2(int idx, long long jlh) {
  if (idx > n) return;
  cnt2++;
  z[cnt2] = (jlh + x[idx]) % m;
  bf2(idx + 1, (jlh + x[idx]) % m);
  bf2(idx + 1, jlh);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = (int)1; i <= (int)n; i++) cin >> x[i];
  bf1(1, 0);
  bf2(18, 0);
  for (int i = (int)1; i <= (int)cnt; i++) {
    y[i] %= m;
  }
  for (int i = (int)1; i <= (int)cnt; i++) mx = max(y[i], mx);
  if (n < 18) {
    cout << mx << endl;
    return 0;
  }
  for (int i = (int)1; i <= (int)cnt2; i++) {
    z[i] %= m;
  }
  for (int i = (int)1; i <= (int)cnt2; i++) mx = max(z[i], mx);
  sort(z + 1, z + 1 + cnt2);
  for (int i = (int)1; i <= (int)cnt; i++) {
    long long le = 1, ri = cnt2, mid, p = 0, res = 0;
    while (le <= ri) {
      mid = le + ri >> 1;
      if (y[i] + z[mid] >= m)
        ri = mid - 1;
      else
        res = mid, le = mid + 1;
    }
    le = 1, ri = res;
    while (le <= ri) {
      mid = (le + ri) / 2;
      if (y[i] + z[mid] >= m)
        ri = mid - 1;
      else
        p = mid, le = mid + 1;
    }
    mx = max((z[p] + y[i]) % m, mx);
    le = res + 1, ri = cnt2;
    while (le <= ri) {
      mid = (le + ri) / 2;
      if (y[i] + z[mid] >= m)
        ri = mid - 1;
      else
        p = mid, le = mid + 1;
    }
    mx = max((z[p] + y[i]) % m, mx);
  }
  cout << mx << endl;
  return 0;
}
