atcoder#ABC281D. [ABC281D] Max Multiple

[ABC281D] Max Multiple

Score : 400400 points

Problem Statement

You are given a sequence of non-negative integers A=(a1,a2,,aN)A=(a_1,a_2,\ldots,a_N).

Let SS be the set of non-negative integers that can be the sum of KK terms in AA (with distinct indices).

Find the greatest multiple of DD in SS. If there is no multiple of DD in SS, print -1 instead.

Constraints

  • 1KN1001 \leq K \leq N \leq 100
  • 1D1001 \leq D \leq 100
  • 0ai1090 \leq a_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN KK DD

a1a_1 \ldots aNa_N

Output

Print the answer.

4 2 2
1 2 3 4
6

Here are all the ways to choose two terms in AA.

  • Choose a1a_1 and a2a_2, whose sum is 1+2=31+2=3.
  • Choose a1a_1 and a3a_3, whose sum is 1+3=41+3=4.
  • Choose a1a_1 and a4a_4, whose sum is 1+4=51+4=5.
  • Choose a2a_2 and a3a_3, whose sum is 2+3=52+3=5.
  • Choose a2a_2 and a4a_4, whose sum is 2+4=62+4=6.
  • Choose a3a_3 and a4a_4, whose sum is 3+4=73+4=7.

Thus, we have S={3,4,5,6,7}S=\{3,4,5,6,7\}. The greatest multiple of 22 in SS is 66, so you should print 66.

3 1 2
1 3 5
-1

In this example, we have S={1,3,5}S=\{1,3,5\}. Nothing in SS is a multiple of 22, so you should print -1.