#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[300000];
int a[40];
int add(int a, int b) { return (a + b >= m) ? a + b - m : a + b; }
void inc(int& a, int b) { a = (a + b >= m) ? a + b - m : a + b; }
int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i] %= m;
  for (int i = 0, len = n / 2; i < (1 << len); i++) {
    int t = 0;
    for (int j = 0; j < len; j++)
      if (i & (1 << j)) inc(t, a[j]);
    f[i] = t;
  }
  sort(f, f + (1 << n / 2));
  int cnt = unique(f, f + (1 << n / 2)) - f;
  int ans = f[cnt - 1];
  for (int i = 0, len = n - n / 2; i < (1 << len); i++) {
    int t = 0;
    for (int j = 0; j < len; j++)
      if (i & (1 << j)) inc(t, a[j + n / 2]);
    ans = max(ans, t);
    int pos = lower_bound(f, f + cnt, m - 1 - t) - f;
    for (int j = max(0, pos - 1); j <= pos + 1; j++) {
      ans = max(ans, add(t, f[j]));
    }
  }
  printf("%d\n", ans);
  return 0;
}
