#include <bits/stdc++.h>
using namespace std;
const int N = 36;
int a[N];
vector<int> v1, v2;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int mask = 0; mask < (1 << (n / 2)); mask++) {
    int sum = 0;
    for (int j = 1; j <= n / 2; j++) {
      if ((mask >> (j - 1)) & 1) {
        sum = (sum + a[j]) % m;
      }
    }
    v1.push_back(sum);
  }
  for (int mask = 0; mask < (1 << (n - n / 2)); mask++) {
    int sum = 0;
    for (int j = n / 2 + 1; j <= n; j++) {
      if ((mask >> (j - n / 2 - 1)) & 1) {
        sum = (sum + a[j]) % m;
      }
    }
    v2.push_back(sum);
  }
  sort(v2.begin(), v2.end());
  int sol = 0;
  for (auto x : v1) {
    int l = 0, r = v2.size() - 1, ans = -1;
    while (l <= r) {
      int mid = l + (r - l) / 2;
      if (v2[mid] <= m - 1 - x) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    if (ans != -1) {
      sol = max(sol, x + v2[ans]);
    }
    sol = max(sol, (x + v2.back()) % m);
  }
  cout << sol << endl;
}
