#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=;

int n,m,jx,a[N],b[M],t1,c[M],t2,ans;

int up(int a,int b){a+=b;a>=m?a-=m:;return a;}

void dfs(int cr,int lm,int lj,bool fx)

{

  if(cr>lm)

    {

      fx?b[++t1]=lj:c[++t2]=lj;

      return;

    }

  dfs(cr+,lm,lj,fx);

  dfs(cr+,lm,up(lj,a[cr]),fx);

}

int main()

{

  scanf("%d%d",&n,&m); jx=n>>;

  for(int i=;i<=n;i++)scanf("%d",&a[i]),a[i]%=m;

  dfs(,jx,,); dfs(jx+,n,,);

  sort(b+,b+t1+); t1=unique(b+,b+t1+)-b-;

  sort(c+,c+t2+); t2=unique(c+,c+t2+)-c-;

  int p0=t2;

  for(int i=;i<=t1;i++)

    {

      while(b[i]+c[p0]>=m)p0--;

      ans=max(ans,b[i]+c[p0]);

    }

  printf("%d\n",ans);

  return ;

}