题目描述

给一个长度为 $\red{n}$的数列和一个整数 $\red{m}$。

在数列任选若干个数，使得它们的和对$\red{m}$取模后最大

输入格式

共两行。

第一行两个正整数$\red{n }$和$\red{m }$。

第二行 $\red{n}$个正整数，表示所给出的数列。

输出格式

一个整数，表示答案

样例

输入样例1

4 4 
5 2 4 1

输出样例1

3

输入样例2

3 20 
199 41 299

输出样例2

19

提示

对于$\red{30\%}$的数据，有$\red{1≤}$$\red{n≤}$$\red{20}$;

对于$\red{100\%}$的数据，有$\red{1≤}$$\red{n≤}$$\red{35, 1≤}$$\red{m, a_i≤}$$\red{10^9}$