Problem 1094 --ZHAN 与糖果

1094: ZHAN 与糖果

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 87  Solved: 14
[Submit][Status][Web Board][Creator:]

Description

ZHAN 很喜欢吃糖果。 

一天,huahua 刚从超市买到一大包糖果,结账出门转角遇到 ZHAN,他紧盯着 huahua 手里的糖果,可 怜的目光使 huahua 停下了脚步。huahua 决定出一个问题,如果 ZHAN 能答对就分一些糖果给他。 

假设 huahua 手里有 n 颗糖果,每颗糖果具有自己的快乐值 ai (1 ≤ i ≤ n),如果 ZHAN 吃掉第 i 颗糖果, 他会获得糖果对应的快乐值。当 ZHAN 获得的快乐值之和是 m 的倍数的时候,ZHAN 就会感到很幸福。 huahua 承诺给 ZHAN 能使他感到很幸福时数量最多的糖果。那么,这部分糖果最多有多少个呢? 

简单来说,假设所有糖果的快乐值构成一个集合 A(允许有重复元素),ZHAN 需要找到这样一个集合 B(允 许有重复元素) 的大小: 

• 1. 集合 B 是 A 的一个子集 

• 2. 集合 B 中所有元素之和为 m 的倍数 

• 3. 集合 B 的是所有满足条件 1 和 2 的集合中元素个数最多的 

虽然这对 ZHAN 来说是道水题,但他现在急于吃糖,无暇思考。你能帮 ZHAN 求出这部分糖果的数量吗?

Input

输入包含两行。 

第一行 2 个整数 n(1 ≤ n ≤ 105 ), m(1 ≤ m ≤ 100). 

第二行 n 个整数 ai (0 ≤ ai ≤ 103 ).

Output

输出一个整数,表示答案。

Sample Input

6 3
1 3 3 5 7 9

Sample Output

5

HINT


样例中ZHAN能得到的糖果是第1、2、3、4、6块,其快乐值之和为3的倍数,且数量最多,故答案为5.



当任意糖果子集快乐值之和不为m倍数时,ZHAN无法获得任何糖果,此时答案为0.

Source

[Submit][Status]