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