#include <bits/stdc++.h>
using namespace std;
set<int> s[40];
set<int>::iterator it, q;
int n, m, k, sol, v[40];
int main() {
  int i, j;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
    v[i] %= m;
  }
  if (n == 1) {
    printf("%d", v[1]);
    return 0;
  }
  if (n == 2) {
    printf("%d", max((v[1] + v[2]) % m, max(v[1], v[2])));
    return 0;
  }
  k = n / 2;
  for (i = 1; i <= n; i++) {
    s[i].insert(v[i]);
    if (i != k + 1) {
      for (it = s[i - 1].begin(); it != s[i - 1].end(); it++) {
        j = *it;
        s[i].insert(j);
        j += v[i];
        j %= m;
        s[i].insert(j);
      }
      s[i - 1].clear();
    }
  }
  it = s[k].end();
  it--;
  sol = *it;
  it = s[n].end();
  it--;
  sol = max(sol, int(*it));
  if (s[n].begin() != s[n].end())
    for (it = s[k].begin(); it != s[k].end(); it++) {
      i = *it;
      j = m - i;
      q = s[n].lower_bound(j);
      if (q != s[n].begin()) {
        q--;
        sol = max(sol, (i + int(*q)) % m);
      }
      q = s[n].end();
      q--;
      sol = max(sol, int((1LL * i + int(*q)) % m));
    }
  printf("%d", sol);
  return 0;
}
