#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[40];
vector<int> b, c;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] %= m;
  }
  int q = n / 2;
  for (int i = 0; i < (1 << q); i++) {
    int s = 0;
    for (int j = 0; j < q; j++) {
      if (i & (1 << j)) s = (s + a[j + 1]) % m;
    }
    b.push_back(s);
  }
  int p = n - q;
  for (int i = 0; i < (1 << p); i++) {
    int s = 0;
    for (int j = 0; j < p; j++) {
      if (i & (1 << j)) s = (s + a[q + j + 1]) % m;
    }
    c.push_back(s);
  }
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  int ans = max(b[b.size() - 1], c[c.size() - 1]);
  for (int i = 0; i < b.size(); i++) {
    if (i && b[i] == b[i - 1]) continue;
    p = upper_bound(c.begin(), c.end(), m - b[i] - 1) - c.begin() - 1;
    if (p >= 0) {
      ans = max(ans, (b[i] + c[p]) % m);
    }
  }
  cout << ans << endl;
  return 0;
}
