#include <bits/stdc++.h>
using namespace std;
const int N = 40, T = 18, MAXN = (1 << T) + 100;
int a[N];
int dp[3][MAXN], n, m;
vector<int> fr, sd;
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 1; i < (1 << min(n, T)); i++) {
    int plcf = __builtin_ctz(i), add = a[plcf] % m;
    dp[0][i] = (dp[0][i ^ (1 << plcf)] + add) % m;
    fr.push_back(dp[0][i]);
  }
  for (int i = 1; i < (1 << max(0, n - T)); i++) {
    int plcf = __builtin_ctz(i), add = a[plcf + T] % m;
    dp[1][i] = (dp[1][i ^ (1 << plcf)] + add) % m;
    sd.push_back(dp[1][i]);
  }
  sd.push_back(0);
  sort(sd.begin(), sd.end());
  int mx = 0;
  fr.push_back(0);
  for (auto x : fr) {
    int nd = m - 1 - x;
    int plc = upper_bound(sd.begin(), sd.end(), nd) - sd.begin() - 1;
    if (plc == sd.size() || plc == 0)
      mx = max(mx, x);
    else
      mx = max(mx, sd[plc] + x);
  }
  cout << mx;
  return 0;
}
