Coinful Escapade

Captain Noir is on the run after his latest daring heist, and fate has lined his escape route with a row of shining coins. Rumor has it that the coins are cursed—if two adjacent coins are picked, an alarm will sound. Ever the risk-taker, Noir devises a meticulous plan: he must select a subset of coins such that no two are consecutive. However, there’s an extra twist imposed by an ancient decree: the total value of the stolen coins must be divisible by an integer $k$.

Given a row of $n$ coins with respective values $c_1, c_2, \dots, c_n$, your task is to help Captain Noir choose a subset (without picking adjacent coins) so that the sum, $S$, of the chosen coins satisfies $S \equiv 0 \pmod{k}$. Of all such possible selections, determine the maximum achievable sum. If it is impossible to obtain a sum divisible by $k$, output $-1$.

Input Format

• The first line contains two space-separated integers $n$ and $k$, where $1 \le n \le 10^5$ and $1 \le k \le 100$.
• The second line contains $n$ space-separated positive integers $c_1, c_2, \dots, c_n$, each representing the value of a coin. It is guaranteed that $1 \le c_i \le 10^9$ for each valid $i$.

Output Format

Output a single integer: the maximum sum obtainable by picking non-adjacent coins such that the sum is divisible by $k$. If no valid selection exists, print $-1$.

Examples

Input

5 3
3 1 4 1 5

Output

12

Input

4 5
2 3 2 3

Output

5