#include <bits/stdc++.h>
using namespace std;
int n, m;
int num[1000010];
int a[1000010], b[1000010];
int sz1 = 0, sz2 = 0, ans = 0;
void dfs1(int dep, int sum) {
  if (dep > n / 2) {
    a[++sz1] = sum;
    return;
  }
  dfs1(dep + 1, (sum + num[dep] % m) % m);
  dfs1(dep + 1, sum);
}
void dfs2(int dep, int sum) {
  if (dep > n) {
    b[++sz2] = sum;
    return;
  }
  dfs2(dep + 1, (sum + num[dep] % m) % m);
  dfs2(dep + 1, sum);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> num[i];
  }
  dfs1(1, 0);
  dfs2(n / 2 + 1, 0);
  sort(a + 1, a + sz1 + 1);
  sort(b + 1, b + sz2 + 1);
  int l = 1, r = sz2;
  while (l <= sz1 && r >= 1) {
    while (a[l] + b[r] >= m && r >= 1) r--;
    ans = max(ans, (a[l] + b[r]) % m);
    if (ans == m - 1) break;
    l++;
  }
  cout << ans << endl;
  return 0;
}
