#include <bits/stdc++.h>
int f(int *a, int begin, int len, int m, int s) {
  int res = 0;
  for (int i = 0; i < len; i++) {
    if ((s & (1 << i)) == 0) continue;
    res = (res + a[begin + i]) % m;
  }
  return res;
}
int binary_search(int *a, int size, int val) {
  if (size == 0) return 0;
  int i = 0, j = size - 1;
  while (i < j) {
    int mid = (j - i) / 2 + i;
    if (a[mid] == val)
      return val;
    else if (a[mid + 1] > val)
      j = mid;
    else
      i = mid + 1;
  }
  return a[i];
}
int main() {
  int n, m, a[36], lhs[1 << 18], rhs[1 << 18];
  while (std::cin >> n >> m) {
    for (int i = 0; i < n; i++) std::cin >> a[i];
    int lhsLen = 1 << (n / 2);
    for (int s = 0; s < lhsLen; s++) {
      lhs[s] = f(a, 0, n / 2, m, s);
    }
    int rhsLen = 1 << (n - n / 2);
    for (int s = 0; s < rhsLen; s++) {
      rhs[s] = f(a, n / 2, n - n / 2, m, s);
    }
    std::sort(rhs, rhs + rhsLen);
    int res = 0;
    for (int i = 0, val; i < lhsLen; i++) {
      val = binary_search(rhs, rhsLen, m - lhs[i] - 1);
      res = std::max(res, (lhs[i] + val) % m);
      val = binary_search(rhs, rhsLen, m * 2 - lhs[i] - 1);
      res = std::max(res, (lhs[i] + val) % m);
    }
    std::cout << res << std::endl;
  }
  return 0;
}
