#include <bits/stdc++.h>
using namespace std;
const int N = (int)3e1 + 7;
int main() {
  int n, m, a[N];
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  if (n == 1) {
    cout << a[n] % m;
    return 0;
  }
  int half = n / 2;
  long long now = 0;
  set<long long> vals;
  for (int mask = 0; mask < (1 << half); mask++) {
    int last = 0;
    long long cur = 0;
    for (int j = 0; j < half; j++) {
      if (mask & (1 << j)) {
        cur += a[j + 1] % m;
        cur %= m;
      }
    }
    vals.insert(cur);
  }
  long long res = 0;
  for (int mask = 0; mask < (1 << (n - half)); mask++) {
    int last = 0;
    long long cur = 0;
    for (int j = 0; j < (n - half); j++) {
      if (mask & (1 << j)) {
        cur += a[half + 1 + j] % m;
        cur %= m;
      }
    }
    int diff = m - cur;
    auto it = vals.lower_bound(diff);
    if (it != vals.begin()) res = max(res, *(--it) + cur);
  }
  cout << res;
  return 0;
}
