You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices \(b_1, b_2, ..., b_k (1 ≤ b_1 < b_2 < ... < b_k ≤ n)\) in such a way that the value of \(\sum^{k}_{i=1}a_{b_i}\) is maximized. Chosen sequence can be empty.

Print the maximum possible value of \(\sum^{k}_{i=1}a_{b_i}\).

Input

The first line contains two integers \(n\) and \(m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10^9)\).

The second line contains \(n\) integers \(a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9)\).

Output

Print the maximum possible value of \(\sum^{k}_{i=1}a_{b_i}\).

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 \(\sum^{k}_{i=1}a_{b_i}\) is equal to \(7\) (and that's \(3\) after taking it modulo \(4\)).

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

题意

给出\(n\)个数，从这\(n\)个数中选出几个数（可以不选），使得这些数的和对\(m\)取余后的值最大

思路

首先有一种特别暴力的方法：枚举出所有的状态后，找出对\(m\)取模后的最大值，时间复杂度\(O(2^n)\)，这里\(n=35\)，肯定是不行的

我们可以将这些数分成两段，分别枚举出这两段的所有状态，对左右两段排序，去重。然后从左半段中选出一个值\(value\)，因为是对\(m\)取模后的最大值，所以最大的结果等于\(m-1\)，在右半段利用二分查找大于\(m-1-value\)的位置\(place\)，右半段\(place-1\)位置的数就是符合要求的数，相加取最大值即可

时间复杂度：\(O(2^{\left \lceil \dfrac {n}{2} \right \rceil}+n)\)

代码

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+10;

const int mod=1e9+7;

const int maxm=1e3+10;

using namespace std;

int a[maxn];

int Left[maxn];

int Right[maxn];

int cntl,cntr;

int n,m;

int main(int argc, char const *argv[])

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt", "r", stdin);

        freopen("out.txt", "w", stdout);

        srand((unsigned int)time(NULL));

    #endif

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>n>>m;

    for(int i=0;i<n;i++)

        cin>>a[i],a[i]%=m;

    int res=0;

    int l,r;

    l=r=n/2;

    for(int i=0;i<(1<<r);i++)

    {

        res=0;

        for(int j=0;j<r;j++)

            if(i>>j&1)

                res+=a[j],res%=m;

        Left[cntl++]=res;

    }

    res=0;

    r=n;

    int num=r-l+1;

    for(int i=0;i<(1<<num);i++)

    {

        res=0;

        for(int j=0;j<num;j++)

            if(i>>j&1)

                res+=a[l+j],res%=m;

        Right[cntr++]=res;

    }

    Left[cntl++]=0;

    Right[cntr++]=0;

    sort(Left,Left+cntl);

    sort(Right,Right+cntr);

    cntl=unique(Left,Left+cntl)-Left;

    cntr=unique(Right,Right+cntr)-Right;

    int ans=0;

    for(int i=0;i<cntl;i++)

    {

        int res=m-Left[i]-1;

        int pos=upper_bound(Right,Right+cntr,res)-Right;

        int num=Right[pos-1];

        ans=max(ans%m,(num+Left[i])%m);

    }

    cout<<ans<<endl;

    #ifndef ONLINE_JUDGE

        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

    #endif

    return 0;

}