# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Collect Coins

By hasan169 · Limits 1s, 512 MB

Mario is playing a game where he has to reach a rock by jumping over n (1 <= n <= 10^5) other rocks. Each rock i has a coin Ai (1 <= i <= n) on them. Mario can either take the coin or he can skip it. Taking a coin will add its value to his score.

Mario can take Ai if, all Aj (1 <= j <= n) such that Ai = Aj and ∑Aj (summation of all Aj) is divisible by k (1 <= k <= 10^3).

After jumping over all the rocks serially, Mario has to maximize his score.

Given n, k and coins value on each of the n rocks, determine the maximum score Mario can get.

## Input

First line of input is a number T (1 <= T <= 10). Each of the next T lines has 2 inputs n, k. Next line will have n inputs for Ai (1 <= Ai <= 10^18).

## Output

For each case there should one number as output. The maximum value. Since the value can be very large, you have to print the value modulo 2^64.

## Sample

InputOutput
1
5 7
14 8 21 14 1

49


### Statistics

62% Solution Ratio

AashiqEarliest, Jan '17

Nasif_44thFastest, 0.1s

Nasif_44thLightest, 918 kB

AlirezaNaShortest, 746B