You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

如果购物不能使你快乐, 那学习一定可以~

题目描述

你来到了一个商场, 现在有 $n$ 件你心仪的商品, 但是你又囊中羞涩, 已知每件商品有一个属性, $x_i$ 表示愉悦值. 现在你想恰好购买 $m$ 件商品, 使得愉悦值之和恰好是 $c$ 的倍数, 并且愉悦值尽可能的大.

数据格式

输入格式

第一行三个整数 $n, m, c$, 表示商品数量, 购买数量, 以及题干中的 $c$

第二行 $n$ 个整数 $x_i$.

输出格式

输出一个整数, 表示满足条件的最大愉悦值, 如果无法满足条件, 则输出 -1

样例

4 2 2
1 2 3 4

6

3 1 2
1 3 5

-1

数据范围

$1 <= n, m, c <= 100$

$1 <= x_i<= 10^9$

注意

需要读写文件, 读入文件名为 shopping.in, 输出文件名为 shopping.out