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 <image> is maximized. Chosen sequence can be empty.

Print the maximum possible value of <image>.

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 <image>.

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 <image> is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {3}.
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a= new int[n];
        for (int i = 0; i < n; i++) {
            a[i] =scanner.nextInt();
            a[i] = a[i] % m;
        }
        int n1 = n / 2;

        int[] a1 = new int[n1 + 1];
        for (int i = 0; i <= n1; i++) {
            a1[i] = 0;
        }

        Set<Integer> b1 = new HashSet<Integer>();
        while (a1[n1] == 0) {
            a1[0]++;
            for (int i = 0; a1[i] == 2; i++) {
                a1[i] = 0;
                a1[i + 1]++;
            }
            int temp = 0;
            for (int i = 0; i < n1; i++) {
                if (a1[i] == 1) {
                    temp = (temp + a[i]) % m;
                }
            }
            b1.add(temp);

        }

        int n2 = n - n1;
        int[] a2 = new int[n2 + 1];
        for (int i = 0; i <= n2; i++) {
            a2[i] = 0;
        }

        Set<Integer> b2 = new HashSet<Integer>();
        while (a2[n2] == 0) {
            a2[0]++;
            for (int i = 0; a2[i] == 2; i++) {
                a2[i] = 0;
                a2[i + 1]++;
            }
            int temp = 0;
            for (int i = 0; i < n2; i++)
                if (a2[i] == 1) {
                    temp = (temp + a[i + n1]) % m;
                }
            b2.add(temp);
        }

        int max = 0;
        for (int i : b1)
            if (i > max) {
                max = i;
            }
        for (int i : b2)
            if (i > max) {
                max = i;
            }
        int b1Size = b1.size();
        int[] c1 = new int[b1Size];
        int count = -1;
        for (int i : b1) {
            count++;
            c1[count] = i;
        }
        int b2Size = b2.size();
        int[] c2 = new int[b2Size];
        count = -1;
        for (int i : b2) {
            count++;
            c2[count] = i;
        }
        Arrays.sort(c2);
        for (int i = 0; i < b1Size; i++) {
            int index = find(c2, m - c1[i]);
            if (c1[i] + c2[index] > max) {
                max = c1[i] + c2[index];
            }
        }
        System.out.print(max);
    }


    public static int find(int[] array, int des) {
        int left = 0;
        int right = Array.getLength(array) - 1;
        int res = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] < des) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        return res;
    }


}
