#include <bits/stdc++.h>
using namespace std;
const int partitionSz2 = 20;
const int partitionSz1 = 15;
long long n, k;
vector<int> p[partitionSz2 + 1];
vector<long long> val;
long long maxValue = 0;
long long getBestValue(long long cur) {
  int curMax = 0;
  int neededValue = k - cur;
  for (int i = 0; i <= partitionSz2; i++) {
    if (p[i].size() == 0) continue;
    auto it = lower_bound(p[i].begin(), p[i].end(), neededValue);
    if (it == p[i].begin()) continue;
    *it--;
    curMax = max(curMax, *it);
  }
  return curMax;
}
void findMaxValue() {
  int sz = min((int)val.size(), partitionSz1);
  for (int msk = 0; msk < 1 << sz; msk++) {
    long long curSum = 0;
    for (int j = 0; j < sz; j++)
      if (msk & (1 << j)) curSum += val[j];
    curSum %= k;
    maxValue = max(maxValue, curSum + getBestValue(curSum));
  }
}
void generateValues() {
  int sz = min((int)val.size() - partitionSz1, partitionSz2);
  sz = max(sz, 0);
  for (int msk = 0; msk < 1 << sz; msk++) {
    long long curSum = 0;
    long long nCount = 0;
    for (int j = 0; j < sz; j++)
      if (msk & (1 << j)) curSum += val[partitionSz1 + j], nCount++;
    p[nCount].push_back(curSum % k);
  }
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    val.push_back(x);
  }
  generateValues();
  for (int j = 0; j <= partitionSz2; j++) sort(p[j].begin(), p[j].end());
  findMaxValue();
  cout << maxValue;
  return 0;
}
