#include <bits/stdc++.h>
using namespace std;
long long a[40];
set<long long> s;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a[i]);
    a[i] %= m;
  }
  int ha = n / 2;
  int _ha = n - ha;
  for (int i = 0; i < (1 << ha); i++) {
    int t = 0;
    for (int j = 0; j < ha; j++)
      if ((1 << j) & i) t = (t + a[j]) % m;
    s.insert(t);
  }
  long long ans = 0;
  set<long long>::iterator it;
  for (int i = 0; i < (1 << _ha); i++) {
    long long t = 0;
    for (int j = 0; j < (_ha); j++)
      if ((1 << j) & i) t = (t + a[j + ha]) % m;
    it = s.upper_bound(m - 1 - t);
    it--;
    ans = max(ans, t + *it);
  }
  cout << ans << endl;
  return 0;
}
