package main

import (
	"fmt"
	"io"
	"os"
	"sort"
)

type FastScanner struct {
	data []byte
	idx  int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data}
}

func (fs *FastScanner) NextInt64() int64 {
	for fs.idx < len(fs.data) {
		c := fs.data[fs.idx]
		if c != ' ' && c != '\n' && c != '\r' && c != '\t' {
			break
		}
		fs.idx++
	}
	var sign int64 = 1
	if fs.idx < len(fs.data) && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	var n int64
	for fs.idx < len(fs.data) {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		n = n*10 + int64(c-'0')
		fs.idx++
	}
	return n * sign
}

func gen(arr []int64, m int64, idx int, cur int64, res *[]int64) {
	if idx == len(arr) {
		*res = append(*res, cur)
		return
	}
	gen(arr, m, idx+1, cur, res)
	gen(arr, m, idx+1, (cur+arr[idx])%m, res)
}

func main() {
	fs := NewFastScanner()
	n := int(fs.NextInt64())
	m := fs.NextInt64()

	a := make([]int64, n)
	for i := 0; i < n; i++ {
		a[i] = fs.NextInt64() % m
	}

	mid := n / 2
	leftArr := a[:mid]
	rightArr := a[mid:]

	leftSums := make([]int64, 0, 1<<len(leftArr))
	rightSums := make([]int64, 0, 1<<len(rightArr))

	gen(leftArr, m, 0, 0, &leftSums)
	gen(rightArr, m, 0, 0, &rightSums)

	sort.Slice(rightSums, func(i, j int) bool { return rightSums[i] < rightSums[j] })

	var ans int64
	for _, x := range leftSums {
		target := m - 1 - x
		pos := sort.Search(len(rightSums), func(i int) bool { return rightSums[i] > target })
		if pos > 0 {
			v := x + rightSums[pos-1]
			if v > ans {
				ans = v
			}
		}
	}

	fmt.Println(ans)
}