#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int a1[N], a2[N], b[1 << 20], c[1 << 20];
int find(int a[], int n, int x) {
  int l = 0, r = n - 1;
  int mid = (l + r) >> 1;
  while (l <= r) {
    if (a[mid] == x)
      return mid;
    else if (a[mid] > x)
      r = mid - 1;
    else
      l = mid + 1;
    mid = (l + r) >> 1;
  }
  if (l >= n) l = n - 1;
  return l;
}
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 0; i < n / 2; i++) scanf("%d", &a1[i]);
    for (int i = 0; i < (n - n / 2); i++) scanf("%d", &a2[i]);
    if (n == 1) {
      printf("%d\n", a2[0] % m);
      continue;
    }
    int num1 = 0, num2 = 0;
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    int n1 = n / 2, n2 = n - (n / 2);
    int ret = 0;
    for (int i = 0; i < (1 << n1); i++) {
      int ans = 0;
      for (int j = 0; j < n1; j++)
        if (i & (1 << j)) ans = (ans + a1[j]) % m;
      b[num1++] = ans;
      ret = max(ret, ans);
    }
    for (int i = 0; i < (1 << n2); i++) {
      int ans = 0;
      for (int j = 0; j < n2; j++)
        if (i & (1 << j)) ans = (ans + a2[j]) % m;
      c[num2++] = ans;
      ret = max(ret, ans);
    }
    sort(b, b + num1);
    sort(c, c + num2);
    for (int i = 0; i < num1; i++) {
      int q = find(c, num2, m - 1 - b[i]);
      if (q && q < num2) ret = max(ret, (c[q - 1] + b[i]) % m);
      ret = max(ret, (c[q] + b[i]) % m);
    }
    printf("%d\n", ret);
  }
  return 0;
}
