#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int AK = 1, IOI = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    AK = ch == '-' ? -1 : 1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    IOI *= 10;
    IOI += ch - 48;
    ch = getchar();
  }
  return AK * IOI;
}
int a[1001];
int f[1001];
inline int Max(int x, int y, int z) {
  int res = x;
  res = std::max(res, y);
  res = std::max(res, z);
  return res;
}
int n, m, middle;
int b_front[1000001];
int b_behind[1000001];
int dl[1000001];
int Dl[1000001];
int dl_front;
int dl_behind;
int number_front;
int number_behind;
inline void dfs(int x, int y) {
  if (x > middle) {
    b_front[++number_front] = y;
    return;
  }
  dfs(x + 1, y);
  dfs(x + 1, (y + a[x]) % m);
}
inline void Dfs(int x, int y) {
  if (x > n) {
    b_behind[++number_behind] = y;
    return;
  }
  Dfs(x + 1, y);
  Dfs(x + 1, (y + a[x]) % m);
}
int main() {
  n = read(), m = read();
  middle = n >> 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    a[i] %= m;
  }
  dfs(1, 0);
  Dfs(middle + 1, 0);
  sort(b_front + 1, b_front + 1 + number_front);
  for (int i = 1; i <= number_front; ++i) {
    if (b_front[i] != b_front[i - 1]) {
      dl[++dl_front] = b_front[i];
    }
  }
  sort(b_behind + 1, b_behind + 1 + number_behind);
  for (int i = 1; i <= number_behind; ++i) {
    if (b_behind[i] != b_behind[i - 1]) {
      Dl[++dl_behind] = b_behind[i];
    }
  }
  int answer = 0;
  int Behind = dl_behind;
  for (int i = 0; i <= dl_front; ++i) {
    while (dl[i] + Dl[Behind] >= m) {
      Behind--;
    }
    answer = std::max(answer, dl[i] + Dl[Behind]);
  }
  answer = std::max(answer, (dl[dl_front] + Dl[dl_behind]) - m);
  printf("%d\n", answer);
}
