#include <bits/stdc++.h>
using namespace std;
int a[1000005], n, m, ans;
set<int> s;
int getint() {
  int ww = 0;
  char cc = getchar();
  while (cc > '9' || cc < '0') cc = getchar();
  while (cc >= '0' && cc <= '9') {
    ww = ww * 10 + cc - '0';
    cc = getchar();
  }
  return ww;
}
long long getll() {
  long long ww = 0;
  char cc = getchar();
  while (cc > '9' || cc < '0') cc = getchar();
  while (cc >= '0' && cc <= '9') {
    ww = ww * 10 + cc - '0';
    cc = getchar();
  }
  return ww;
}
void setup() {
  n = getint();
  m = getint();
  for (int i = (1); i <= (n); i++) a[i] = (getint() % m);
}
void work() {
  int k = n / 2;
  n -= k;
  for (int i = (1); i <= ((1 << k) - 1); i++) {
    int sum = 0;
    for (int j = (0); j <= (k - 1); j++)
      if ((i >> j) & 1) sum = (sum + a[j + 1]) % m;
    ans = max(ans, sum);
    s.insert(sum);
  }
  for (int i = (1); i <= ((1 << n) - 1); i++) {
    int sum = 0;
    for (int j = (0); j <= (n); j++)
      if ((i >> j) & 1) sum = (sum + a[j + 1 + k]) % m;
    ans = max(ans, sum);
    set<int>::iterator it = s.lower_bound(m - sum);
    if (it == s.begin()) continue;
    it--;
    ans = max(ans, sum + *it);
  }
  printf("%d", ans);
}
int main() {
  setup();
  work();
  return 0;
}
