#include<bits/stdc++.h>

using namespace std;

const int inf=0x3f3f3f3f;

int n;
long long a[50];
long long m,ans=-inf;
int cnt=0,cnt1=0,cnt2=0;
long long l[(1<<20)+10],r[(1<<20)+10];

inline void dfs(int x,int y,long long now,long long f[]){
	if(x>y){
		f[++cnt]=now;
		return;
	}
	dfs(x+1,y,now,f);
	dfs(x+1,y,now+a[x],f);
}

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

	dfs(1,n/2,0,l);
	cnt1=cnt;
	cnt=0;
	dfs(n/2+1,n,0,r);
	cnt2=cnt;
	
	sort(r+1,r+1+cnt2);
	for(int i=1;i<=cnt1;i++){
        int p1=(lower_bound(r+1,r+1+cnt2,m-l[i])-(r+1));
        if(p1>=0){
            ans=max(ans,(l[i]+r[p1])%m);
        }
        int p2=(lower_bound(r+1,r+1+cnt2,2*m-l[i])-(r+1));
        if(p2>=0){
            ans=max(ans,(l[i]+r[p2])%m);
        }
    }
	printf("%lld\n",ans);
	return 0;
}