You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n) in such a way that the value of is maximized. Chosen sequence can be empty.

Print the maximum possible value of .

Input

The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print the maximum possible value of .

Examples

Input

4 4

5 2 4 1

Output

3

Input

3 20

199 41 299

Output

19

Note

In the first example you can choose a sequence b = {1, 2}, so the sum is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {3}.

题意：

给你一个数组a，和一个数m，让你选出一个数组a的子集，让子集中的数的sum和对m取模后的数值最大。

思路：

meet-in-the-middle 的思路，把数组分成两个部分，每一个部分数最多就是 35/2 的大小，对于每一个部分，我们通过二进制枚举所有状态， 把第一部分的所有子集的sum和求出（同意取模），然后第二部分同样的操作，把取模后的sum分别加入到数组v1和v2中，最后对于第一部分的每一个数x，去第二部分中找一个数y，使之(x+y )%m 尽量大。

那么x+y 分为两种情况，

当x+y 大于等于m，

那么结果是 x+y-m 的，那么这里的y我们不妨选择最大的，这样可以使数值更大。

反之就是 x+y<m

y要是小于m-x 中的最大值，这样x+y 更接近m-1

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

inline void getInt(int* p);

const int maxn=1000010;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll a[60];

std::vector<ll> v1;

std::vector<ll> v2;

ll haf;

ll n,m;

void dfs1(int id,ll num)

{

	v1.pb(num%m);

	if(id<=haf)

	{

		dfs1(id+1,num);

		dfs1(id+1,num+a[id]);

	}

}

void dfs2(int id,ll num)

{

	v2.pb(num%m);

	if(id<=n)

	{

		dfs2(id+1,num);

		dfs2(id+1,num+a[id]);

	}

}

int main()

{

    // freopen("D:\\code\\text\\input.txt","r",stdin);

	//freopen("D:\\code\\text\\output.txt","w",stdout);

	gbtb;

	cin>>n>>m;

	repd(i,1,n)

	{

		cin>>a[i];

		a[i]%=m;

	}

	haf=(n>>1);

	dfs1(1,0ll);

	dfs2(haf+1,0ll);

	sort(ALL(v1));

	sort(ALL(v2));

	v1.erase(unique(ALL(v1)),v1.end());

	v2.erase(unique(ALL(v2)),v2.end());

	ll ans=0ll;

	int p=sz(v2);

	int q=sz(v1);

	for(auto x:v1)

	{

		int pos=lower_bound(ALL(v2),m-x)-v2.begin();

		if(pos>=1&&pos<p)

		{

			ans=max(ans,(x+v2[pos-1])%m);

		}

		ans=max(ans,(x+v2[p-1])%m);

	}

	cout<<ans<<endl;

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}