#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const long long inf = 1e18;
const long long maxn = (1 << 18) + 50;
const int mod = 1e9 + 7;
long long T, n, m, k;
long long a[50];
long long _left[maxn];
long long _right[maxn];
bool check(long long k, long long mid) {
  if (k + _right[mid] < m) {
    return true;
  }
  return false;
}
bool check2(long long k, long long mid) {
  if (k + _right[mid] < m * 2) {
    return true;
  }
  return false;
}
int main() {
  long long allans = 0;
  memset(_left, 0, sizeof(_left));
  scanf("%I64d%I64d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  for (int i = 1; i < (1 << ((n / 2))); i++) {
    for (int j = 1; (1 << (j - 1)) <= i; j++) {
      int s = 1 << (j - 1);
      if (i & s) {
        _left[i] = (_left[i] + a[j]) % m;
        allans = max(allans, _left[i]);
      }
    }
  }
  sort(_left + 1, _left + (1 << (n / 2)));
  memset(_right, 0, sizeof(_right));
  int ends = (1 << ((n - n / 2)));
  _right[ends] = inf;
  for (int i = 1; i < (1 << ((n - n / 2))); i++) {
    for (int j = 1; (1 << (j - 1)) <= i; j++) {
      int s = 1 << (j - 1);
      if (i & s) {
        _right[i] = (_right[i] + a[j + n / 2]) % m;
        allans = max(_right[i], allans);
      }
    }
  }
  sort(_right + 1, _right + (1 << (n - n / 2)));
  for (int i = 1; i < (1 << ((n / 2))); i++) {
    long long k = _left[i];
    long long st = 0, ed = (1 << (n - n / 2));
    while (ed - st > 1) {
      long long mid = st + (ed - st) / 2;
      if (check(k, mid)) {
        st = mid;
      } else
        ed = mid;
    }
    long long ans1 = (_right[st] + k) % m;
    allans = max(ans1, allans);
    st = 0;
    ed = (1 << (n - n / 2));
    while (ed - st > 1) {
      long long mid = st + (ed - st) / 2;
      if (check2(k, mid)) {
        st = mid;
      } else
        ed = mid;
    }
    long long ans2 = (_right[st] + k) % m;
    allans = max(ans2, allans);
  }
  printf("%I64d\n", allans);
  return 0;
}
