#include <bits/stdc++.h>
using namespace std;
int n, m, v[41], st[41], niv, suma, maxim, f[51], dp1[1000001], dp2[1000001];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    v[i] = v[i] % m;
  }
  sort(v + 1, v + n + 1);
  niv = 1;
  int nr1 = n / 2;
  int nr2 = n - nr1;
  for (int i = 0; i < (1 << nr1); i++) {
    long long suma = 0;
    for (int j = 0; j < nr1; j++)
      if ((i >> j) & 1) suma = (suma + v[j + 1]) % m;
    dp1[i + 1] = suma;
    if (dp1[i + 1] > maxim) maxim = dp1[i + 1];
  }
  for (int i = 0; i < (1 << nr2); i++) {
    long long suma = 0;
    for (int j = 0; j < nr2; j++)
      if ((i >> j) & 1) suma = (suma + v[j + 1 + nr1]) % m;
    dp2[i + 1] = suma;
    if (dp2[i + 1] > maxim) maxim = dp2[i + 1];
  }
  int lg1 = (1 << nr1);
  int lg2 = (1 << nr2);
  sort(dp2 + 1, dp2 + lg2 + 1);
  for (int i = 1; i <= lg1; i++) {
    int pozmax = 0;
    int st = 1;
    int dr = lg2;
    while (st <= dr) {
      int mij = (st + dr) / 2;
      if (dp1[i] + dp2[mij] < m) {
        if (mij > pozmax) pozmax = mij;
        st = mij + 1;
      } else
        dr = mij - 1;
    }
    if ((dp1[i] + dp2[pozmax]) % m > maxim) maxim = dp1[i] + dp2[pozmax];
    pozmax = 0;
    st = 1;
    dr = lg2;
    while (st <= dr) {
      int mij = (st + dr) / 2;
      if (dp1[i] + dp2[mij] < 2 * m) {
        if (mij > pozmax) pozmax = mij;
        st = mij + 1;
      } else
        dr = mij - 1;
    }
    if ((dp1[i] + dp2[pozmax]) % m > maxim) maxim = dp1[i] + dp2[pozmax];
  }
  cout << maxim;
  return 0;
}
