Stressful Training
Contest: Educational Codeforces Round 61 (Rated for Div. 2)
Difficulty rating: 2300
Tags: binary search, greedy

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
2 4
3 2
4 2

Example output:
5

Example input:
1 5
4
2

Example output:
1

Editorial:
The easiest part of the solution is to notice that if the charger of power $$$x$$$ works then the charger of power $$$x + 1$$$ also works. Thus, binary search is applicable to the problem.
$$$k$$$ is really small and only one laptop can be charged during some minute. It implies that check function can work in something polynomial on $$$k$$$ by searching for the right laptop to charge during every minute.
I claim that the greedy algorithm works. Find the laptop that gets his charge below zero the first. Charge it for one minute as early as possible. Repeat until you either don't have time to charge the laptop (check returns false) or the contest is over (check returns true).
Why greedy works? Well, check any case where check returns false. If some laptop runs out of power then all the minutes up to the current one are used to charge something. Moreover, you can free no minute of these as by doing greedy we charged all laptops as late as possible. Freeing some minute will lead to other laptop dying earlier.
One way to implement this is the following. Keep a heap of events ($$$time\_i-th\_laptop\_dies$$$), pop its head, add $$$x$$$ to it if the time is greater than the number of charges already made and push it back to heap. That will simulate the entire process in $$$O((n + k) \log n)$$$. Unfortunately, this may be too slow on some implementations.
Let's try the following linear approach. Maintain not the heap but such an array that $$$i$$$-th its cell contains all indices of all the laptops to run out of charge on the beginning of minute $$$i$$$. Keep an iterator to the first non-empty position. Pop a single index out of this vector, charge it and push it to the new position. You'll still make $$$k$$$ steps and on each step you'll make $$$O(1)$$$ instant operations. That will make it $$$O(n + k)$$$ for this simulation.
I'm not really sure how to build the maximal answer case, however, I can estimate the upper bound of binary search. You can set $$$x$$$ in such a way that it charges every laptop in one minute so that it won't run out of power until the end of the contest. Choose the smallest $$$a_i$$$, the greatest $$$b_i$$$, the greatest $$$k$$$ and you'll end up with $$$1 - 2 \cdot 10^5 \cdot 10^7$$$ total usage. Thus, $$$2 \cdot 10^12$$$ will always be enough.
Overall complexity: $$$O((n + k) \cdot \log ANS)$$$. (or $$$O((n + k) \cdot \log ANS \log n)$$$ if you are skillful enough to squeeze it :D).