普及⏱ 1000ms💾 256MB#P5126🏷️ 动态规划

题目描述

促销日全场 $N$ 件商品,每件含不同数量的积分。会员可以任选若干件带走(每件至多一件),要求所选商品的积分总和是 $K$ 的整数倍——这样才能把积分平均分给团队成员。在满足整除的前提下,积分总和越大越好。

求能带走的最大积分总和;若无法凑出 $K$ 的倍数,输出 0。

输入格式

第一行两个整数 $N, K$,用空格分隔。 随后 $N$ 行,每行一个整数,为该件商品的积分。

输出格式

一行,一个整数:满足整除条件的最大积分总和;无法凑出输出 0。

数据范围

$$1 \le N \le 100,\quad 1 \le K \le 100,\quad \text{单件积分} \le 10^6$$

样例输入 #1
5 7
1
2
3
4
5
样例输出 #1
14
样例输入 #2
1 1
1000000
样例输出 #2
1000000