#872 チョンリンのゲーム開発 (Hard)

問題文

問題文の言語

チョンリンはゲームを開発したいと思っていたが、これまで何度もプロジェクトが中断した経験と先行きへの不安から、新しいプロジェクトを始められずにいた。考えた末、シオンを雇って作業を任せることにした。

現在、ゲームのプロジェクトには $N$ 個の作業がある。作業 $i$ の進捗は $a_i$ であり、シオンがその作業を $1$ 日行うと、進捗が $b_i$ 増加する。

シオンは毎日、相異なる作業をちょうど $K$ 個選んで行う。選んだ各作業 $i$ の進捗は $b_i$ 増加し、選ばなかった作業の進捗は変化しない。進捗に上限はない。

チョンリンは、すべての作業の進捗が等しくなるまで、シオンに毎日働いてもらうつもりである。

すべての作業の進捗を等しくするために必要な最小の日数を求めよ。最初からすべての進捗が等しい場合、答えは $0$ である。不可能な場合、答えは -1 である。

入力は以下の形式で与えられる。

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

すべての作業の進捗を等しくするために必要な最小の日数を出力せよ。不可能な場合は -1 を出力せよ。

#	得点	制約
1	13	$b_i=1$ ( $1\le i\le N$ ).
2

例 1

入力例

2
1 2
1 1

出力例

$1$ 日目に作業 $1$ と $2$ を選ぶと、進捗はそれぞれ $2$ と $1$ 増加し、すべての進捗が $[2,2,2]$ になる。