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_{i = 1}^{k} a_{b_{i}} \operatorname{mod} m$ is maximized. Chosen sequence can be empty.

Print the maximum possible value of $\sum_{i = 1}^{k} a_{b_{i}} \operatorname{mod} m$.


-----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_{i = 1}^{k} a_{b_{i}} \operatorname{mod} m$.


-----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_{i = 1}^{k} 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}.

Difficulty: interview

Starter code:

Solutions:
import bisect

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

# n : number of integers
# m : mod

half_n = n // 2

a1, a2 = a[:half_n], a[half_n:]

n1, n2 = len(a1), len(a2)

r1, r2 = [], []

def dfs1(i, sum):
    if i == n1:
        r1.append(sum)
    else:
        dfs1(i+1, sum)
        dfs1(i+1, (sum+a1[i])%m)

def dfs2(i, sum):
    if i == n2:
        r2.append(sum)
    else:
        dfs2(i+1, sum)
        dfs2(i+1, (sum+a2[i])%m)

dfs1(0,0)
dfs2(0,0)

r1, r2 = [sorted(set(x)) for x in [r1, r2]]

ans = 0

for i, x in enumerate(r1):
    p = bisect.bisect_left(r2, m-x)
    tmp_ans = r2[p-1] + x
    if tmp_ans > ans:
        ans = tmp_ans

print(ans)











n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))
a2=sorted(set(a2))
for i in a2:
    j=bisect.bisect_left(a1,m-i)
    ans=max(ans,a1[j-1]+i)
print(ans)
    
    
    
    
    


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    ans=max(ans,a1[j-1]+i)
print(ans)
    
    
    
    
    


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=set(),set()
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.add(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.add(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    ans=max(ans,a1[j-1]+i)
print(ans)
    


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in range(len(a2)):
    j=bisect.bisect_left(a1,m-a2[i])
    ans=max(ans,a1[j-1]+a2[i])
print(ans)
    
    


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    ans=max(ans,a1[j-1]+i)
    k=a1[j-1]+i
    if ans<k:
        ans=k
print(ans)
    
    


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    k=a1[j-1]+i
    if ans<k:
        ans=k
print(ans)


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=set(),set()
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.add(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.add(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(a1)

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
a=[int(i) for i in input().split()]
import bisect
a1,a2=[],[]
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
import array
a1,a2=array.array('L'),array.array('L')
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


import bisect
import array
n,m=list(map(int,input().split()))
a=array.array('L',list(map(int,input().split())))
a1,a2=array.array('L'),array.array('L')
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=array.array('L',sorted(set(a1)))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


import bisect
import array
n,m=list(map(int,input().split()))
a=array.array('L',list(map(int,input().split())))
a1,a2=array.array('L'),array.array('L')
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)
k=0
sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=array.array('L',sorted(set(a1)))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


import bisect
import array
n,m=list(map(int,input().split()))
a=array.array('L')
a.extend(list(map(int,input().split())))
a1,a2=array.array('L'),array.array('L')
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=array.array('L',sorted(set(a1)))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


import bisect
import array
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a1,a2=array.array('L'),array.array('L')
n1=n//2

def sums1(i,sum=0):
    if i==n1:
        a1.append(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        a2.append(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=array.array('L',sorted(set(a1)))

for i in a2:
    j=bisect.bisect_left(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2
app1=a1.append
app2=a2.append
def sums1(i,sum=0):
    if i==n1:
        app1(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        app2(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))
bis=bisect.bisect_left
def solve(i):
    nonlocal ans
    j=bis(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
    return ans
l=list(map(solve,a2))
print(l[-1])


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2
app1=a1.append
app2=a2.append
def sums1(i,sum=0):
    if i==n1:
        app1(sum)
    else:
        sums1(i+1,(sum+a[i])%m)
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        app2(sum)
    else:
        sums2(i+1,(sum+a[i])%m)
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))
bis=bisect.bisect_left
for i in a2:
    j=bis(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
print(ans)


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
import bisect
a1,a2=[],[]
n1=n//2
app1=a1.append
app2=a2.append
def sums1(i,sum=0):
    if i==n1:
        app1(sum%m)
    else:
        sums1(i+1,(sum+a[i]))
        sums1(i+1,sum)
        
def sums2(i,sum=0):
    if i==n:
        app2(sum%m)
    else:
        sums2(i+1,(sum+a[i]))
        sums2(i+1,sum)

sums1(0)
sums2(n1)

ans=0
end=len(a2)-1

a1=sorted(set(a1))
bis=bisect.bisect_left
def solve(i):
    nonlocal ans
    j=bis(a1,m-i)
    if ans<a1[j-1]+i:
        ans=a1[j-1]+i
    return ans
l=list(map(solve,a2))
print(l[-1])

n,m=list(map(int,input().split()))
a=[int(i)%m for i in input().split()]
x,y=set(),set()
def f(x,n,i,s=0):
    if i==n:
        x.add(s)
    else:
        f(x,n,i+1,(s+a[i])%m)
        f(x,n,i+1,s)
h=n//2
f(x,h,0)
f(y,n,h)
y=sorted(y)
import bisect
k=0
print(max(i+y[bisect.bisect_left(y,m-i)-1]for i in x))


from bisect import *
f = lambda: map(int, input().split())
n, m = f()
t = list(f())
def g(x, i, n, s):
    if i < n:
        g(x, i + 1, n, s + t[i])
        g(x, i + 1, n, s)
    else: x.add(s % m)
k = n >> 1
x, y = set(), set()
g(x, 0, k, 0)
g(y, k, n, 0)
y = sorted(y)
print(max(i + y[bisect_left(y, m - i) - 1] for i in x))

n,m=map(int,input().split())
a=[int(i) for i in input().split()]
x,y=set(),set()
def f(x,n,i,s=0):
    if i==n:x.add(s%m)
    else:
        f(x,n,i+1,s+a[i])
        f(x,n,i+1,s)
h=n//2
f(x,h,0)
f(y,n,h)
y=sorted(y)
import bisect
k=0
print(max(i+y[bisect.bisect_left(y,m-i)-1]for i in x))

n,m=list(map(int,input().split()))
l=[int(i) for i in input().split()]
first=l[:n//2]
sec=l[n//2:]
n1=n//2 
n2=n//2+n%2 
t1=(1<<n1)
t2=(1<<n2)
s1=[]
for i in range(t1):
    now=0 
    for j in range(len(first)):
        if i&(1<<j):
            now+=first[j]
    s1.append(now%m)
s2=[]
for i in range(t2):
    now= 0 
    for j in range(len(sec)):
        if i&(1<<j):
            now+=sec[j]
    s2.append(now%m)
s1.sort()
s2.sort() 
maxi=0 
def check(l,x): #largest number less than x in l  # l is asc 
    lo=0 
    hi=len(l)-1 
    ans=0 
    while lo<=hi: 
        mi=(lo+hi)>>1 
        if l[mi]<x:
            ans=l[mi] 
            lo=mi+1
        else:
            hi=mi-1 
    return ans 
for i in s1:
    req=m-i 
    pair=check(s2,req)
    maxi=max(maxi,(i+pair)%m)
print(maxi)