청린의 게임개발 (Hard)

청린은 게임을 개발하고 싶었지만, 여러 차례 프로젝트가 중단된 경험과 막막함 때문에 새로운 프로젝트를 시작하지 못하고 있었다. 고민 끝에 청린은 시온을 고용해 일을 시키기로 했다.

현재 청린의 게임 프로젝트에는 $N$개의 작업이 있다. $i$번째 작업의 진행도는 $a_i$이며, 시온이 해당 작업을 하루 동안 수행하면 진행도가 $b_i$만큼 증가한다.

시온은 하루에 서로 다른 작업을 정확히 $K$개 선택하여 수행한다. 선택한 각 작업 $i$의 진행도는 $b_i$만큼 증가하고, 선택하지 않은 작업의 진행도는 변하지 않는다. 작업의 진행도에는 상한이 없다.

청린은 모든 작업의 진행도가 같아질 때까지 시온에게 매일 일을 시키려고 한다.

시온을 위해 모든 작업의 진행도를 같게 만드는 데 필요한 최소 일수를 구해주자. 처음부터 모든 작업의 진행도가 같다면 필요한 일수는 $0$이다. 모든 작업의 진행도를 같게 만들 수 없다면 -1을 정답으로 한다.

입력은 다음과 같은 형식으로 주어진다.

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

모든 작업의 진행도를 같게 만드는 데 필요한 최소 일수를 출력한다. 모든 작업의 진행도를 같게 만들 수 없다면 -1을 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le K \le N$.
• $0\le a_i\le {10}^9$ ().