给一个数列和m，在数列任选若干个数，使得他们的和对m取模后最大（ (1<=n<=35) , (1<=m<=10^{9})）
考虑把数列分成两份，两边分别暴力求出所有的可能，那么对于一个数列中每一个数字(x)，另一个数列加上它之后小于(m)的那个数是最优的，用双指针可以做到(O(2^{n/2}))
如果最终的答案是两个数列中的数加起来且大于(m)的，因为所有可能都是在模意义下，所以肯定是两个数列中最大的数加起来最优，判断一下就好了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='
';
}
const int N=(1<<18)+5;
int n,P,lim,f[N],g[N],a[55],tf,tg,ans;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
void dfs1(int pos,int lim,int res){
if(pos==lim)return (void)(f[++tf]=res,f[++tf]=add(res,a[pos]));
dfs1(pos+1,lim,res),dfs1(pos+1,lim,add(res,a[pos]));
}
void dfs2(int pos,int lim,int res){
if(pos==lim)return (void)(g[++tg]=res,g[++tg]=add(res,a[pos]));
dfs2(pos+1,lim,res),dfs2(pos+1,lim,add(res,a[pos]));
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),P=read(),lim=n>>1;
fp(i,1,n)a[i]=read()%P;
if(n==1)return printf("%d
",a[1]),0;
dfs1(1,lim,0),dfs2(lim+1,n,0);
sort(f+1,f+1+tf),sort(g+1,g+1+tg);
for(R int i=1,j=tg;i<=tf;++i){
while(f[i]+g[j]>=P)--j;
cmax(ans,f[i]+g[j]);
}cmax(ans,f[tf]+g[tg]-P);
printf("%d
",ans);return 0;
}