#include <bits/stdc++.h>
using namespace std;
long long n, m, tmp;
long long a[40];
vector<long long> v1, v2;
map<long long, long long> mp;
void solve(long long i, long long sum) {
  if (i == tmp) return;
  if (mp[sum] == 0) {
    v1.push_back(sum);
    mp[sum]++;
  }
  if (mp[(sum + a[i]) % m] == 0) {
    v1.push_back((sum + a[i]) % m);
    mp[(sum + a[i]) % m] = 1;
  }
  solve(i + 1, sum % m);
  solve(i + 1, (sum + a[i]) % m);
}
void solve1(long long i, long long sum) {
  if (i == n) return;
  if (mp[sum] == 0) {
    v2.push_back(sum);
    mp[sum]++;
  }
  if (mp[(sum + a[i]) % m] == 0) {
    v2.push_back((sum + a[i]) % m);
    mp[(sum + a[i]) % m] = 1;
  }
  solve1(i + 1, sum % m);
  solve1(i + 1, (sum + a[i]) % m);
}
int main() {
  cin >> n >> m;
  long long i, j, k, l;
  for (i = 0; i < n; i++) cin >> a[i];
  tmp = n / 2;
  solve(0, 0);
  mp.clear();
  solve1(tmp, 0);
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  long long ans = 0;
  if (n == 1) {
    cout << a[0] % m;
    return 0;
  }
  for (i = 0; i < v1.size(); i++) {
    auto it = lower_bound(v2.begin(), v2.end(), m - v1[i]);
    it--;
    ans = max(ans, *it + v1[i]);
  }
  cout << ans;
}
