H. Space Bar
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The annual ICPC (Intergalactic Collegiate Programming Contest) competition is ready to welcome its guests again (this time, fortunately, without any postponements). Among the participants is the well-known team from the Honourable School of Experts, which, according to this year's rules, consists of exactly $$$n$$$ members. The $$$i$$$-th team member evaluates their problem-solving ability at exactly $$$a_i$$$ units.

Deciding not to break the good tradition, the team members decided to visit the equally famous bar "DRYga" on the evening before the start of the main tour. Since the team is quite experienced, they are aware of an interesting pattern that is characteristic of them. Initially, the $$$i$$$-th team member is able to solve exactly $$$0$$$ problems in the competition. After each "special extreme shot" is consumed, the strength of the $$$i$$$-th team member is enhanced by $$$k$$$, allowing him to solve exactly $$$(x + k) \bmod (a_i + 1)$$$ problems in the competition, where $$$x$$$ is the number of problems the member could solve before taking the shot, and $$$a \bmod b$$$ is the operation of taking the remainder of the integer division of $$$a$$$ by $$$b$$$. Throughout the evening, the team only orders "special extreme shots" of strength $$$k$$$, and each team member can order an unlimited number of shots.

Since the team is determined to win the competition this year, they want to order exactly the number of "special extreme shots" of strength $$$k$$$ so that each team member can solve exactly $$$a_i$$$ problems. Help the legendary team calculate the minimum total number of shots they need to order at the bar.

Input

The first line of the input contains two natural numbers $$$n$$$ and $$$k$$$ separated by a space — the number of team members and the strength of the "special extreme shot".

The second line of the input contains $$$n$$$ natural numbers $$$a_1, a_2, a_3, \ldots, a_n$$$ — the problem-solving ability of the $$$i$$$-th team member.

$$$$$$ 1 \le n \le 10^5 $$$$$$ $$$$$$ 1 \le k \le 10^5 $$$$$$ $$$$$$ 0 \le a_i \le 10^5 $$$$$$ $$$$$$ \sum{a_i} \le 10^6 $$$$$$

Output

Output a single number — the minimum number of shots that the team needs to order.

If there is no such quantity of shots for each team member to solve exactly $$$a_i$$$ problems, output $$$-1$$$.

Examples
Input
5 5
1 2 3 5 7
Output
9
Input
5 6
28 16 4 18 20
Output
-1
Note

In the first example, team members with numbers $$$1$$$, $$$2$$$, and $$$4$$$ need to order one shot each to solve the required number of problems, while the rest of the team members need to order exactly three shots each to solve the required number of problems for them.