#include<bits/stdc++.h>
using namespace std;
#define int int
int a[1000005];
int sum[1000005];
signed main(){
	int n,mod;
	cin>>n>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int m=n/2,k=n-m;
	for(int i=0;i<(1<<m);i++){
		for(int j=1;j<=m;j++){
			sum[i]+=((i>>(j-1))&1)*a[m-j+1];
		}
		sum[i]%=mod;
	}
	sort(sum,sum+(1<<m));
	int ans=0;
	for(int i=0;i<(1<<k);i++){
		int s=0;
		for(int j=1;j<=k;j++){
			s+=((i>>(j-1))&1)*a[n-j+1]; 
		}
		s%=mod;
		int x=(lower_bound(sum,sum+(1<<m),(mod-1-s))-sum); 
		int mx=0;
		if(x>0&&x<m-1){
			mx=max((sum[x]+s)%mod,max((sum[x-1]+s)%mod,(sum[x+1]+s)%mod));
		}
		if(x<=0){
			mx=max((sum[x]+s)%mod,(sum[x+1]+s)%mod);
		}
		if(x>=m-1){
			mx=max((sum[x]+s)%mod,(sum[x-1]+s)%mod);
		}
		ans=max(ans,mx);
	}
	cout<<ans;
	return 0;
}