#include <bits/stdc++.h>
using namespace std;
int n, m, a[40], ans;
vector<int> vec;
void f(int nn, int id) {
  int x = 0;
  if (id == 2) x = n / 2;
  for (int i = 0; i < (1 << nn); i++) {
    int rs = 0;
    for (int j = 0; j < nn; j++) {
      if ((i >> j) & 1) {
        rs += a[j + 1 + x];
        rs %= m;
      }
    }
    rs %= m;
    if (id == 1)
      vec.push_back(rs);
    else {
      ans = max(rs, ans);
      auto p = upper_bound(vec.begin(), vec.end(), m - 1 - rs);
      if (p == vec.begin()) continue;
      p--;
      ans = max(ans, rs + *p);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] %= m;
  }
  f(n / 2, 1);
  sort(vec.begin(), vec.end());
  f(n - n / 2, 2);
  cout << ans;
}
