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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Divide and conquer

Complete search


Solutions:
from bisect import bisect_right, bisect_left
import sys

def input():
	return sys.stdin.buffer.readline().rstrip()
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
la = a[:n // 2]
ra = a[n // 2:]
La = [0]
Ra = [0]
len_la = len(la)
for i in range(1 << len_la):
	v = 0
	V = i
	for bit in range(len_la):
		if V & 1:
			v += la[bit]
		V >>= 1
	La.append(v % m)
len_ra = len(ra)
for i in range(1 << len_ra):
	v = 0
	V = i
	for bit in range(len_ra):
		if V & 1:
			v += ra[bit]
		V >>= 1
	Ra.append(v % m)
ans = 0
La.sort()
Ra.sort()
for v in La:
	ans = max(ans, v + Ra[bisect_right(Ra, m - 1 - v) - 1])
print(ans)


(n, m) = 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)


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)))


from sys import stdin
from bisect import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
a = gil()

def getSubsetSum(a):
	vals = set([0])
	tmp = []
	ans = 0
	for v in a:
		for ov in vals:
			tmp.append((ov + v) % m if ov + v >= m else v + ov)
		while tmp:
			if len(tmp) >= 10000000.0:
				print('fuvk')
				exit()
			ans = max(ans, tmp[-1])
			vals.add(tmp.pop())
	return sorted(vals)
p = n & 1
(l, r) = (getSubsetSum(a[:n // 2 + p]), getSubsetSum(a[n // 2 + p:]))
ans = 0
(nl, nr) = (len(l), len(r))
for v in l:
	i = bisect_left(r, m - v)
	if i:
		ans = max(ans, r[i - 1] + v)
	i = bisect_left(r, 2 * m - v)
	if i:
		ans = max(ans, (r[i - 1] + v) % m)
print(ans)


(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):
	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)


import bisect
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
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
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):
	global 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])


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1

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)
for _ in range(t):
	(n, m) = li()
	a = li()
	h = n // 2
	x = set()
	y = set()
	f(x, h, 0)
	f(y, n, h)
	y = sorted(y)
	s = 0
	for i in x:
		j = bisect_left(y, m - 1 - i)
		if j != len(y):
			if (y[j] + i) % m < m:
				s = max(s, (y[j] + i) % m)
		if j > 0:
			if (y[j - 1] + i) % m < m:
				s = max(s, (y[j - 1] + i) % m)
	wi(s)


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
p = n // 2
q = n - p
B = A[0:p]
C = A[p:n]
S = []
for i in range(2 ** p):
	s = 0
	for j in range(p):
		if i >> j & 1:
			s += B[j]
	s %= m
	S.append(s)
T = []
for i in range(2 ** q):
	t = 0
	for j in range(q):
		if i >> j & 1:
			t += C[j]
	t %= m
	T.append(t)
T.sort()
ans = -1
import bisect
for s in S:
	idx = bisect.bisect_right(T, m - 1 - s)
	if idx != 0:
		ans = max(ans, max((s + T[idx - 1]) % m, (s + T[-1]) % m))
	else:
		ans = max(ans, (s + T[-1]) % m)
print(ans)


def fckset(arr, i, ans, m, s):
	if i == len(arr):
		s.add(ans)
	else:
		fckset(arr, i + 1, (ans + arr[i]) % m, m, s)
		fckset(arr, i + 1, ans, m, s)
(n, m) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
x = set()
y = set()
h1 = fckset(arr[:n // 2], 0, 0, m, x)
h2 = fckset(arr[n // 2:], 0, 0, m, y)
x = list(x)
y = list(y)
y.sort()
import bisect
print(max((i + y[bisect.bisect_left(y, m - i) - 1] for i in x)))


from bisect import bisect_left
t = []

def f(lst, i, e, m, s=0):
	if i == e:
		t.append(s % m)
	else:
		f(lst, i + 1, e, m, s)
		f(lst, i + 1, e, m, s + lst[i])
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = n // 2
l1 = a[0:d]
l2 = a[d:]
f(l1, 0, d, m)
a1 = t
t = []
f(l2, 0, len(l2), m)
a2 = t
a1.sort()
a2.sort()
ans = 0
for x in a1:
	i = bisect_left(a2, m - x)
	val = (x + a2[i - 1]) % m
	ans = max(ans, val)
print(ans)


lst1 = []
lst2 = []
sec_sum1 = []
sec_sum2 = []

def rec1(pos, sum):
	if pos == len(lst1):
		sec_sum1.append(sum)
		return
	rec1(pos + 1, (sum + lst1[pos]) % m)
	rec1(pos + 1, sum)

def rec2(pos, sum):
	if pos == len(lst2):
		sec_sum2.append(sum)
		return
	rec2(pos + 1, (sum + lst2[pos]) % m)
	rec2(pos + 1, sum)

def binary_search(key, high):
	(hi, lo, mid, ans) = (len(sec_sum2) - 1, 0, 0, 0)
	while hi >= lo:
		mid = int((hi + lo) / 2)
		if key + sec_sum2[mid] == high:
			return high
		elif key + sec_sum2[mid] < high:
			lo = mid + 1
			ans = mid
		else:
			hi = mid - 1
	return key + sec_sum2[ans]
(n, m) = map(int, input().split(' '))
A = [int(a) for a in input().split()]
for i in range(0, n, 1):
	if i % 2 == 0:
		lst1.append(A[i] % m)
	else:
		lst2.append(A[i] % m)
rec1(0, 0)
rec2(0, 0)
sec_sum1.sort()
sec_sum2.sort()
maxi = 0
for i in range(0, len(sec_sum1), 1):
	cur = binary_search(sec_sum1[i], m - 1)
	maxi = max(maxi, cur)
print(maxi)


import sys
from bisect import bisect_left
(n, m) = map(int, input().split())
a = list(map(int, input().split()))

def solve(a):
	res = [0]
	for x in a:
		res.extend([(x + y) % m for y in res])
	return sorted(set(res))
(pre, suf) = (solve(a[:n // 2]), solve(a[n // 2:]))
suf_n = len(suf)
ans = 0
for x in pre:
	i = bisect_left(suf, (m - x - 1) % m) % suf_n
	ans = max(ans, (x + suf[i - 1]) % m, (x + suf[i]) % m, (x + suf[(i + 1) % suf_n]) % m)
print(ans)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l = [l[i] % k for i in range(n)]
if n == 1:
	print(l[0])
	sys.exit(0)
l1 = l[:n // 2]
l2 = l[n // 2:]
s = set()
s1 = set()
s2 = set()
for i in range(n // 2):
	for j in s:
		s2.add((j + l1[i]) % k)
	s.add(l1[i])
	for j in s2:
		s.add(j)
	s2 = set()
for i in range(n - n // 2):
	for j in s1:
		s2.add((j + l2[i]) % k)
	s1.add(l2[i])
	for j in s2:
		s1.add(j)
	s2 = set()
s = list(s)
s1 = list(s1)
s.sort()
s1.sort()
ans = max(max(s), max(s1))
for i in range(len(s)):
	t = k - 1 - s[i]
	ind = binarySearchCount(s1, len(s1), t)
	r = s1[ind - 1]
	rt = s1[-1]
	t = ans
	ans = max((r + s[i]) % k, (s[i] + rt) % k)
	ans = max(ans, t)
print(ans)


import os, sys
from io import BytesIO, IOBase

def gen(x, m):
	bt = []
	for i in range(len(x)):
		for xx in range(len(bt)):
			bt.append((bt[xx] + x[i]) % m)
		bt.append(x[i] % m)
	return sorted(set(bt))

def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 1:
		print(arr[0] % m)
		exit()
	a = gen(arr[n // 2:], m)
	b = gen(arr[:n // 2], m)
	ans = max((a[-1] + b[-1]) % m, a[-1] % m, b[-1] % m)
	j = len(b) - 1
	for i in range(len(a)):
		ans = max(ans, (a[i] + b[j]) % m)
		while j != -1 and a[i] + b[j] >= m:
			j -= 1
			ans = max(ans, (a[i] + b[j]) % m)
		if j == -1:
			break
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
(n, M) = tuple(map(int, input().split()))
nums = list(map(int, input().split()))
(r1, r2) = ([], [])

def dfs(index, last, sum, check):
	if index == last:
		if check == 1:
			r1.append(sum)
		else:
			r2.append(sum)
		return
	dfs(index + 1, last, sum, check)
	dfs(index + 1, last, (sum + nums[index]) % M, check)
dfs(0, n // 2, 0, 1)
dfs(n // 2, n, 0, 2)
s1 = set()
s2 = set()
for i in r1:
	s1.add(i)
for i in r2:
	s2.add(i)
r1 = sorted(list(s1))
r2 = sorted(list(s2))
ans = 0
for x in r1:
	p = bisect.bisect_left(r2, M - x)
	ans = max(ans, x + r2[p - 1])
print(ans)


import bisect
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
b = []
otv = 0
for i in range(0, 1 << n // 2 + n % 2):
	t = 0
	k = i
	for j in range(20):
		if k & 1:
			t += a[j]
		k = k >> 1
	b.append(t % m)
b.sort()
for i in range(0, 1 << n // 2):
	t = 0
	k = i
	for j in range(20):
		if k & 1:
			t += a[n // 2 + n % 2 + j]
		k = k >> 1
	t = t % m
	k = bisect.bisect_left(b, m - t - 1)
	if k < len(b):
		t2 = b[k]
		if t2 > m - t - 1:
			if k - 1 >= 0:
				t2 = b[k - 1]
	else:
		t2 = b[-1]
	otv = max(otv, (t + t2) % m, (t + b[-1]) % m)
print(otv % m)


def Anal(A, i, r, m, S):
	if i == len(A):
		S.add(r)
	else:
		Anal(A, i + 1, (r + A[i]) % m, m, S)
		Anal(A, i + 1, r, m, S)
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
x = set()
y = set()
Anal(A[:n // 2], 0, 0, m, x)
Anal(A[n // 2:], 0, 0, m, y)
x = sorted(x)
y = sorted(y)
import bisect
print(max((i + y[bisect.bisect_left(y, m - i) - 1] for i in x)))