#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 15;
const int inf = 0x3f3f3f3f;
int a[N];
int b[N], bp;
void dfs1(int i, int n, int mod, long long sum) {
  if (i > n) {
    b[bp++] = sum % mod;
    return;
  }
  dfs1(i + 1, n, mod, sum + a[i]);
  dfs1(i + 1, n, mod, sum);
}
void dfs2(int i, int n, int mod, long long sum, int& ans) {
  if (i > n) {
    sum = sum % mod;
    int pos = lower_bound(b, b + bp, mod - sum) - b;
    if (pos != 0) {
      ans = max(ans, (int)(b[pos - 1] + sum));
    }
    pos = lower_bound(b, b + bp, 2 * mod - sum) - b;
    if (pos != 0) {
      ans = max(ans, (int)(b[pos - 1] + sum) % mod);
    }
    return;
  }
  dfs2(i + 1, n, mod, sum + a[i], ans);
  dfs2(i + 1, n, mod, sum, ans);
}
int main() {
  int n, mod;
  while (~scanf("%d%d", &n, &mod)) {
    bp = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int ans = 0;
    dfs1(1, (n + 1) / 2, mod, 0);
    sort(b, b + bp);
    bp = unique(b, b + bp) - b;
    dfs2((n + 1) / 2 + 1, n, mod, 0, ans);
    printf("%d\n", ans);
  }
}
