#include <bits/stdc++.h>
using namespace std;
map<int, int> map1;
map<int, map<int, int> > map2;
long long int X[2000005], Y[2000005];
void calcsubarray(long long int a[], long long int x[], int n, int c,
                  long long int M) {
  for (int i = 0; i < (1 << n); i++) {
    long long int s = 0;
    for (int j = 0; j < n; j++)
      if (i & (1 << j)) s = (s + a[j + c]) % M;
    x[i] = (s) % M;
  }
}
long long int solve(long long int a[], int n, long long int m) {
  calcsubarray(a, X, n / 2, 0, m);
  calcsubarray(a, Y, n - n / 2, n / 2, m);
  int size_X = 1 << (n / 2);
  int size_Y = 1 << (n - n / 2);
  sort(Y, Y + size_Y);
  long long int ans = 0;
  for (int i = 0; i < size_X; i++) {
    long long int curr = X[i];
    curr = m - curr - 1;
    int p = lower_bound(Y, Y + size_Y, curr) - Y;
    if (p == size_Y || Y[p] != curr) p--;
    if ((Y[p] + X[i]) % m > ans) ans = Y[p] + X[i];
    ans = max(ans, X[i]);
  }
  for (int i = 0; i < size_Y; i++) {
    ans = max(ans, Y[i]);
  }
  return ans;
}
int main() {
  int N;
  scanf("%d", &N);
  long long int M;
  scanf("%lld", &M);
  long long int A[N + 1];
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  printf("%lld\n", solve(A, N, M));
  return 0;
}
