#include <bits/stdc++.h>
using namespace std;
int n, m, it, it2, len;
int a[36], q[500010], p[500010];
int ret = 0;
void init(int step, int sum) {
  if (step == len)
    q[++it] = sum, q[++it] = (sum + a[step]) % m;
  else {
    init(step + 1, (sum + a[step]) % m);
    init(step + 1, sum);
  }
}
void init2(int step, int sum) {
  if (step == n)
    p[++it2] = sum, p[++it2] = (sum + a[step]) % m;
  else {
    init2(step + 1, (sum + a[step]) % m);
    init2(step + 1, sum);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (n == 1) {
    printf("%d", a[1] % m);
    return 0;
  }
  len = n / 2;
  init(1, 0);
  init2(len + 1, 0);
  sort(q + 1, q + it + 1);
  sort(p + 1, p + it2 + 1);
  for (int i = 1; i <= it; i++) {
    int l = 1, r = it2, want = m - q[i] - 1, ans = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (p[mid] <= want) {
        ans = mid;
        l = mid + 1;
      } else
        r = mid - 1;
    }
    if (ans == -1) {
      ret = max(ret, (q[i] + p[it2]) % m);
    } else {
      ret = max(ret, (q[i] + p[ans]) % m);
    }
  }
  ret = max(ret, max(q[it], p[it2]));
  printf("%d", ret);
  return 0;
}
