#include <bits/stdc++.h>
using namespace std;
int N, M;
int A[40];
vector<int> va, vb;
int ans;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    A[i] %= M;
  }
  if (N == 1) {
    cout << A[1] << '\n';
    return 0;
  }
  int md = N / 2;
  int vas = md, vbs = N - md;
  int msk = (1 << vas);
  for (int mi = 0; mi <= msk - 1; mi++) {
    int tmp = 0;
    for (int b = 0; b <= vas - 1; b++)
      if ((!!(mi & (1 << b)))) tmp = (tmp + A[b + 1]) % M;
    va.push_back(tmp);
    ans = max(ans, tmp);
  }
  msk = (1 << vbs);
  for (int mi = 0; mi <= msk - 1; mi++) {
    int tmp = 0;
    for (int b = 0; b <= vbs - 1; b++)
      if ((!!(mi & (1 << b)))) tmp = (tmp + A[md + b + 1]) % M;
    vb.push_back(tmp);
    ans = max(ans, tmp);
  }
  sort(va.begin(), va.end());
  sort(vb.begin(), vb.end());
  for (int vi : va) {
    int oth = M - vi;
    auto it = lower_bound(vb.begin(), vb.end(), oth);
    if (it == vb.begin()) continue;
    it--;
    ans = max(ans, *it + vi);
  }
  cout << ans << '\n';
  return 0;
}
