#include <bits/stdc++.h>
using namespace std;
vector<int> ti[2];
vector<int> sum[2];
int n, m;
void all_possible(int type, int i, int val) {
  if (i == ti[type].size()) {
    sum[type].push_back(val);
    return;
  }
  all_possible(type, i + 1, val);
  all_possible(type, i + 1, (val + ti[type][i]) % m);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    if (i < n / 2)
      ti[0].push_back(x);
    else
      ti[1].push_back(x);
  }
  all_possible(0, 0, 0);
  all_possible(1, 0, 0);
  sort(sum[0].begin(), sum[0].end());
  sort(sum[1].begin(), sum[1].end());
  sum[0].erase(unique(sum[0].begin(), sum[0].end()), sum[0].end());
  sum[1].erase(unique(sum[1].begin(), sum[1].end()), sum[1].end());
  int re = 0;
  for (auto it : sum[0]) {
    int val = it;
    int baki = m - it - 1;
    auto it1 = upper_bound(sum[1].begin(), sum[1].end(), baki);
    if (it1 != sum[1].begin()) {
      it1--;
      val += *it1;
    }
    re = max(re, val);
  }
  printf("%d\n", re);
  return 0;
}
