CF1132D.Stressful Training

Berland SU holds yet another training contest for its students today. $n$ students came, each of them brought his laptop. However, it turned out that everyone has forgot their chargers!

Let students be numbered from $1$ to $n$. Laptop of the $i$-th student has charge $a_i$ at the beginning of the contest and it uses $b_i$ of charge per minute (i.e. if the laptop has $c$ charge at the beginning of some minute, it becomes $c - b_i$ charge at the beginning of the next minute). The whole contest lasts for $k$ minutes.

Polycarp (the coach of Berland SU) decided to buy a single charger so that all the students would be able to successfully finish the contest. He buys the charger at the same moment the contest starts.

Polycarp can choose to buy the charger with any non-negative (zero or positive) integer power output. The power output is chosen before the purchase, it can't be changed afterwards. Let the chosen power output be $x$. At the beginning of each minute (from the minute contest starts to the last minute of the contest) he can plug the charger into any of the student's laptops and use it for some integer number of minutes. If the laptop is using $b_i$ charge per minute then it will become $b_i - x$ per minute while the charger is plugged in. Negative power usage rate means that the laptop's charge is increasing. The charge of any laptop isn't limited, it can become infinitely large. The charger can be plugged in no more than one laptop at the same time.

The student successfully finishes the contest if the charge of his laptop never is below zero at the beginning of some minute (from the minute contest starts to the last minute of the contest, zero charge is allowed). The charge of the laptop of the minute the contest ends doesn't matter.

Help Polycarp to determine the minimal possible power output the charger should have so that all the students are able to successfully finish the contest. Also report if no such charger exists.

今日，贝尔兰德国立大学（Berland SU）再次为其学生举办了一场训练赛。共有 $n$ 名学生参加，每人携带了自己的笔记本电脑。然而，令人尴尬的是，所有人都忘记带充电器了！

将学生编号为 $1$ 至 $n$。第 $i$ 名学生的笔记本电脑在比赛开始时的电量为 $a_i$，且每分钟消耗 $b_i$ 单位电量（即：若某分钟初笔记本电量为 $c$，则下一分钟初电量变为 $c - b_i$）。整场比赛持续 $k$ 分钟。

波利卡普（Berland SU 的教练）决定购买一个充电器，以确保所有学生都能顺利完成比赛。他将在比赛开始的同时购买该充电器。

波利卡普可选择购买任意非负（即零或正）整数功率输出的充电器。功率输出需在购买前选定，之后不可更改。设所选功率输出为 $x$。在每分钟初（从比赛开始的第一分钟到比赛最后一分钟），他可将充电器插入任意一名学生的笔记本电脑，并连续使用若干整数分钟。若某笔记本电脑原本每分钟耗电 $b_i$，则在充电器接入期间，其每分钟耗电量变为 $b_i - x$。若该值为负，则表示笔记本电脑电量在增加。笔记本电脑的电量无上限，可无限增长。充电器在同一时刻最多只能接入一台笔记本电脑。

若某名学生的笔记本电脑在比赛期间（从比赛开始的第一分钟到最后一分钟）的每一分钟初电量均不低于零（允许为零），则该学生被视为成功完成比赛。比赛结束当分钟的电量无需考虑。

请帮助波利卡普确定：为使所有学生均能成功完成比赛，充电器所需的最小可能功率输出；若不存在满足条件的充电器，请予以说明。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 2 \cdot 10^5$) — the number of students (and laptops, correspondigly) and the duration of the contest in minutes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$) — the initial charge of each student's laptop.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^7$) — the power usage of each student's laptop.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 2 \cdot 10^5$）—— 分别表示学生（以及对应笔记本电脑）的数量和比赛持续的分钟数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{12}$）—— 表示每位学生笔记本电脑的初始电量。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^7$）—— 表示每位学生笔记本电脑的功耗。

Print a single non-negative integer — the minimal possible power output the charger should have so that all the students are able to successfully finish the contest.

If no such charger exists, print -1.

输出一个非负整数——充电器所需的最小功率，使得所有学生都能成功完成比赛。

若不存在满足条件的充电器，则输出 $-1$。

Let's take a look at the state of laptops in the beginning of each minute on the first example with the charger of power $5$:

1. charge: $[3, 2]$, plug the charger into laptop 1;
2. charge: $[3 - 4 + 5, 2 - 2] = [4, 0]$, plug the charger into laptop 2;
3. charge: $[4 - 4, 0 - 2 + 5] = [0, 3]$, plug the charger into laptop 1;
4. charge: $[0 - 4 + 5, 3 - 2] = [1, 1]$.

The contest ends after the fourth minute.

However, let's consider the charger of power $4$:

1. charge: $[3, 2]$, plug the charger into laptop 1;
2. charge: $[3 - 4 + 4, 2 - 2] = [3, 0]$, plug the charger into laptop 2;
3. charge: $[3 - 4, 0 - 2 + 4] = [-1, 2]$, the first laptop has negative charge, thus, the first student doesn't finish the contest.

In the fourth example no matter how powerful the charger is, one of the students won't finish the contest.

让我们考察第一个样例中，功率为 $5$ 的充电器在每分钟开始时笔记本电脑的状态：

1. 电量：$[3, 2]$，将充电器接入笔记本电脑 1；
2. 电量：$[3 - 4 + 5, 2 - 2] = [4, 0]$，将充电器接入笔记本电脑 2；
3. 电量：$[4 - 4, 0 - 2 + 5] = [0, 3]$，将充电器接入笔记本电脑 1；
4. 电量：$[0 - 4 + 5, 3 - 2] = [1, 1]$。

比赛在第四分钟后结束。

然而，考虑功率为 $4$ 的充电器：

1. 电量：$[3, 2]$，将充电器接入笔记本电脑 1；
2. 电量：$[3 - 4 + 4, 2 - 2] = [3, 0]$，将充电器接入笔记本电脑 2；
3. 电量：$[3 - 4, 0 - 2 + 4] = [-1, 2]$，第一台笔记本电脑电量为负，因此第一位学生无法完成比赛。

在第四个样例中，无论充电器功率多高，总有一位学生无法完成比赛。