#include<bits/stdc++.h>

using namespace std;

#define int long long 


int n,m; 
int a[33],sum[33];
int sum1[200000]; 
int sum2[200000];
int k1=1,k2=1;
map<int,int>mp1,mp2;
 
 void fun(int x,int y,int k)
 {
 	if(k==1)
 	{
 		for(int i=x;i<=y;i++)
 		{
 			int l=k1;
 			if(mp1[a[i]]==0)
 			{
 				mp1[a[i]]++;
				sum1[k1]=a[i]%m;
				k1++;	
			}
			
			for(int j=0;j<l;j++)
			{
				if(mp1[(sum1[j]+a[i])%m]==0)
				{
					mp1[(sum1[j]+a[i])%m]++;
					sum1[k1]=(sum1[j]+a[i])%m;
					k1++;
				}
			}
			//cout << sum1[k1]+a[i] << " 1\n";
		}
		
	}
	if(k==2)
	{
		for(int i=x;i<=y;i++)
 		{
 			int l=k2;
 			if(mp2[a[i]]==0)
 			{
 				mp2[a[i]]++;
				sum2[k2]=a[i]%m;
				k2++;	
			}
			for(int j=0;j<l;j++)
			{
				if(mp2[(sum2[j]+a[i])%m]==0)
				{
					mp2[(sum2[j]+a[i])%m]++;
					sum2[k2]=(sum2[j]+a[i])%m;
					k2++;
				}
			}
			//cout << sum2[k2]+a[i] << " 2\n";
		}
		
	}
}

signed main()
{
  //int n,m;
  cin >> n >> m;
  for(int i=1;i<=n;i++)cin >> a[i];
  fun(1,n/2,1);
  fun(n/2+1,n,2);
  sort(sum1+1,sum1+k1);
  sort(sum2+1,sum2+k2);
  int ans=0;
//  for(int i=1;i<k1;i++)cout << sum1[i] << ' ';
//  cout << "  111\n";
//  for(int i=1;i<k2;i++)cout << sum2[i] << " ";
//  cout << "  2222\n";
  for(int i=1;i<k1;i++)
  {
  	int k=m-sum1[i]-1;
  	int l=1,r=k2-1;
  	while(l<r)
  	{
  		if(ans==m-1)
  		{
  			break;
		}
  		int mid=(l+r)/2;
		if(sum2[mid]>k)r=mid-1;
		else if(sum2[mid]<k)l=mid+1;
		else ans=m-1;	
	}
	if(ans==m-1)
  	{
  		break;
	}
	if(sum2[l]>k||l==k2)l--;
	ans=max(ans,sum1[i]+sum2[l]);
	//cout << l << "   333\n";
  }
  cout << ans;
  return 0;
}