include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 40;
int n,m;
int a[N];

void dfs(int u,int ed,int sum,vector[HTML_REMOVED] &way)
{
if(u == ed)
{
way.push_back(sum); // 如果搜到ed位的数字了，说明搜完了
return; // 基准条件，避免死循环
}

dfs(u+1,ed,sum,way);    // 没有加这一位的情况
dfs(u+1,ed,sum+a[u],way);   // 加了这一位的情况

}

int main()
{
cin >> n >> m;

for(int i = 0 ; i < n ;  i++)   cin >> a[i];

// dfs顺序：这个数字选或者不选
// 因为一棵树耗时太大了，所以这里用双向dfs法，用空间换时间

vector<int> A,B;    // 开两个动态数组存储两半的每一种情况

dfs(0,n/2,0,A);     // 从第0位开始搜索，一直搜到第n/2位，搜出来一种情况就存在s里，s初始化为0，最后把所有情况加在A组里面
dfs(n/2,n,0,B);

// 此时已经找到了A组和B组的所有情况
// 分别对其取模
for(auto &x:A)     x %= m;
for(auto &x:B)     x %= m;

// 然后排序
sort(A.begin(),A.end());
sort(B.begin(),B.end());

// 排完序后找A和B的最大值
int res = max(A.back(),B.back());
int tmp = (A.back() + B.back()) % m;    // A.back() + B.back() 一定会落在[m, …, 2m-2]这个区间内，而在这个区间内值越大余数越大，所以在A[i]+B[i] > m 这个情况下，(A.back() + B.back()) % m 一定是最大余数

res = max(res,tmp);

// 再找A[i]+B[j] < m 的情况
for(int i = 0 ,j = B.size() - 1 ; i < A.size() ; i ++)
{
    while(j >= 0 && A[i] + B[j] >= m) j--;    // 跳过所有A[i] + B[j] >= m 的情况，因为这种情况的最大值已经找出来是res了
    if(j >= 0)  res = max(res,A[i] + B[j]);     // 如果A[i] + B[j] < m,再分别讨论即可
}

cout << res;

return 0;

}