You are given an array *a* consisting of *n* integers, and additionally an integer *m*. You have to choose some sequence of indices *b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*k*</sub> (1 ≤ *b*<sub class="lower-index">1</sub> &lt; *b*<sub class="lower-index">2</sub> &lt; ... &lt; *b*<sub class="lower-index">*k*</sub> ≤ *n*) in such a way that the value of <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b62c0a7977dc1ab5f3cef631b6eb630ef6d7b8b3.png" style="max-width: 100.0%;max-height: 100.0%;"/> is maximized. Chosen sequence can be empty.

Print the maximum possible value of <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b62c0a7977dc1ab5f3cef631b6eb630ef6d7b8b3.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 35, 1 ≤ *m* ≤ 10<sup class="upper-index">9</sup>).

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
In the first example you can choose a sequence *b* = {1, 2}, so the sum <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/c856546022c2feee13d02a4ec9cd1d361ab3a756.png" style="max-width: 100.0%;max-height: 100.0%;"/> is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence *b* = {3}.
4 4
5 2 4 1
3
3 20
199 41 299
19
5 10
47 100 49 2 56
9
5 1000
38361 75847 14913 11499 8297
917
10 10
48 33 96 77 67 59 35 15 14 86
9
10 1000
16140 63909 7177 99953 35627 40994 29288 7324 44476 36738
999
30 10
99 44 42 36 43 82 99 99 10 79 97 84 5 78 37 45 87 87 11 11 79 66 47 100 8 50 27 98 32 27
9
30 1000
81021 18939 94456 90340 76840 78808 27921 71826 99382 1237 93435 35153 71691 25508 96732 23778 49073 60025 95231 88719 61650 50925 34416 73600 7295 14654 78340 72871 17324 77484
999
35 10
86 66 98 91 61 71 14 58 49 92 13 97 13 22 98 83 85 29 85 41 51 16 76 17 75 25 71 10 87 11 9 34 3 6 4
9
35 1000
33689 27239 14396 26525 30455 13710 37039 80789 26268 1236 89916 87557 90571 13710 59152 99417 39577 40675 25931 14900 86611 46223 7105 64074 41238 59169 81308 70534 99894 10332 72983 85414 73848 68378 98404
999
35 1000000000
723631245 190720106 931659134 503095294 874181352 712517040 800614682 904895364 256863800 39366772 763190862 770183843 774794919 55669976 329106527 513566505 207828535 258356470 816288168 657823769 5223226 865258331 655737365 278677545 880429272 718852999 810522025 229560899 544602508 195068526 878937336 739178504 474601895 54057210 432282541
999999999
35 982451653
27540278 680344696 757828533 487257472 581415866 897315944 104006244 109795853 24393319 840585536 643747159 864374693 675946278 27492061 172462571 484550119 801174500 94160579 818984382 53253720 966692115 811281559 154162995 890236127 799613478 611617443 787587569 606421577 91876376 464150101 671199076 108388038 342311910 974681791 862530363
982451652
15 982451653
384052103 7482105 882228352 582828798 992251028 892163214 687253903 951043841 277531875 402248542 499362766 919046434 350763964 288775999 982610665
982368704
35 1000000000
513 9778 5859 8149 297 7965 7152 917 243 4353 7248 4913 9403 6199 2930 7461 3888 1898 3222 9424 3960 1902 2933 5268 2650 1687 5319 5065 8450 141 4219 2586 2176 1118 9635
158921
35 982451653
5253 7912 3641 7428 6138 9613 9059 6352 9070 89 9030 1686 3098 7852 3316 8158 7497 5804 130 6201 235 64 3451 6104 4148 3446 6059 6802 7466 8781 1636 8291 8874 8924 5997
197605
15 982451653
7975 7526 1213 2318 209 7815 4153 1853 6651 2880 4535 587 8022 3365 5491
64593
35 1730970
141538 131452 93552 3046 119468 8282 166088 33782 36462 25246 178798 81434 180900 15102 175898 157782 155254 166352 60772 75162 102326 104854 181138 58618 123800 54458 157516 20658 25084 155276 194920 16680 15148 188292 88802
1730968
35 346194136
89792 283104 58936 184528 194768 253076 304368 140216 220836 69196 274604 68988 300412 242588 25328 183488 81712 374964 377696 317872 146208 147400 346276 14356 90432 347556 35452 119348 311320 126112 113200 98936 189500 363424 320164
6816156
35 129822795
379185 168630 1047420 892020 180690 1438200 168330 1328610 933930 936360 1065225 351990 1079190 681510 1336020 814590 365820 1493580 495825 809745 309585 190320 1148640 146790 1008900 365655 947265 1314060 1048770 1463535 1233420 969330 1324530 944130 1457160
29838960
35 106920170
36941450 53002950 90488020 66086895 77577045 16147985 26130825 84977690 87374560 59007480 61416705 100977415 43291920 56833000 12676230 50531950 5325005 54745005 105536410 76922230 9031505 121004870 104634495 16271535 55819890 47603815 85830185 65938635 33074335 40289655 889560 19829775 31653510 120671285 37843365
106907815
35 200000000
75420000 93400000 70560000 93860000 183600000 143600000 61780000 145000000 99360000 14560000 109280000 22040000 141220000 14360000 55140000 78580000 96940000 62400000 173220000 40420000 139600000 30100000 141640000 64780000 186080000 159220000 137780000 133640000 83560000 51280000 139100000 133020000 99460000 35900000 78980000
199980000
4 1
435 124 324 2
0
1 12
13
1
1 1000000000
1000000000
0
7 19
8 1 4 8 8 7 3
18
6 7
1 1 1 1 1 6
6
3 5
1 2 3
4
4 36
22 9 24 27
33
2 8
7 1
7
2 12
8 7
8
4 10
11 31 12 3
7
2 8
2 7
7
4 19
16 20 19 21
18
3 4
9 16 11
3
2 3
3 7
1
2 20
4 3
7
3 299
100 100 200
200
#include <utility>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;

typedef vector<int> vi;

void foreach_sum(vi & a, int m, function<void(int)> callback) {
    function<void(int, int, function<void(int)>)> recur;
    recur = [&recur, &a, m](int i, int sum, function<void(int)> callback) {
        if (i == a.size()) {
            callback(sum);
            return;  
        }
        recur(i + 1, (a[i] + sum) % m, callback);
        recur(i + 1, sum, callback);
    };
    recur(0, 0, callback);
}

#define MAX(a, b) ( ((a) > (b)) ? (a) : (b) )
int f(vi *a, int m) {
    vi sums[2];
    for (int i = 0; i < 2; ++i) {
        foreach_sum(a[i], m, [&sums, i](int sum) {
            sums[i].push_back(sum);
        });
    }
    sort(sums[0].begin(), sums[0].end());
    
    int max = 0;
    for (int x : sums[1]) {
        auto it = lower_bound(sums[0].begin(), sums[0].end(), m - 1 - x);
        if (it == sums[0].end() || *it > m - 1 - x) {
            max = MAX(*(it - 1) + x, max);
        } else {
            max = m - 1;
        }
    }
    return max;
}


int main() {
    int n, m;
    cin >> n >> m;
    vi a[2];
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        a[i % 2].push_back(t);
    }
    cout << f(a, m) << endl;
}