#872 Cheongrin's Game Development (Hard)

Statement

Statement language

Cheongrin wanted to develop a game, but repeated abandoned projects and uncertainty had kept him from starting a new one. After some thought, he hired Sion to work on the project.

The game project currently has $N$ tasks. Task $i$ has progress $a_i$ . If Sion works on this task for one day, its progress increases by $b_i$ .

Each day, Sion chooses exactly $K$ distinct tasks to work on. The progress of each chosen task $i$ increases by $b_i$ , and the progress of every other task stays unchanged. There is no upper limit on progress.

Cheongrin plans to have Sion work every day until all tasks have equal progress.

Find the minimum number of days needed to make the progress of all tasks equal. If all tasks already have equal progress, the answer is $0$ . If it is impossible, the answer is -1.

Input

The input is given in the following format:

$N\ K$ $a_1\ a_2\ \cdots\ a_N$

Output

Print the minimum number of days needed to make all tasks have equal progress. If it is impossible, print -1.

Constraints

$1 \le N \le 200\,000$ .
$1 \le K \le N$ .
$0 \leq a_{i} \leq 10^{9}$ ().

Subtasks

#	Score	Constraints
1	13	$b_i=1$ ( $1\le i\le N$ ).

Samples

Sample 1

Input

2
1 2
1 1

Output

1

On the first day, choose tasks $1$ and $2$ . Their progress increases by $2$ and $1$ , respectively, so the progress values become $[2,2,2]$ .