#include <bits/stdc++.h>
using namespace std;
const int e = 40;
int n;
long long m, a[e], ans = 0;
vector<long long> ve[2];
set<long long> se[2];
void dfs(int pl, int sum, int lim, int t) {
  sum %= m;
  if (!se[t].count(sum)) ve[t].push_back(sum);
  if (pl > lim) return;
  dfs(pl + 1, (sum + a[pl]) % m, lim, t);
  dfs(pl + 1, sum, lim, t);
}
bool cmp(long long aa, long long bb) { return aa > bb; }
int main() {
  scanf("%d", &n);
  scanf("%lld", &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] %= m;
  }
  dfs(1, 0, n / 2, 0);
  dfs(n / 2 + 1, 0, n, 1);
  int len1 = ve[0].size(), len2 = ve[1].size();
  int pl1 = 0, pl2 = len2;
  sort(ve[0].begin(), ve[0].end());
  sort(ve[1].begin(), ve[1].end());
  for (int i = len1 - 1; i > -1; i--) {
    while (ve[0][i] + ve[1][pl1] < m and pl1 < len2) {
      ans = max(ans, ve[0][i] + ve[1][pl1]);
      pl1++;
    }
  }
  cout << ans;
}
