#include <bits/stdc++.h>
using namespace std;
int main() {
  set<long long> st;
  long long n, m;
  cin >> n >> m;
  long long x;
  for (int i = 0; i < n / 2 + n % 2; i++) {
    cin >> x;
    vector<long long> a;
    for (auto i : st) a.push_back(-i + x);
    st.insert(-(x % m));
    for (auto i : a) st.insert(-(i % m));
  }
  st.insert(0);
  long long mx = 0;
  vector<long long> a(n / 2);
  for (int i = 0; i < n / 2; i++) {
    cin >> a[i];
    a[i] = a[i] % m;
  }
  for (int i = 0; i < (1 << (n / 2)); i++) {
    long long x = i;
    long long t = 0;
    for (int j = 0; j < n / 2; j++) {
      if (x % 2 == 1) t = (t + a[j]) % m;
      x >>= 1;
    }
    mx = max(mx, (-*st.begin() + t) % m);
    mx = max(mx, (-*st.lower_bound(-m + t + 1) + t));
  }
  cout << mx;
  return 0;
}
