CF1132D.Stressful Training

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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

Let students be numbered from 11 to nn . Laptop of the ii -th student has charge aia_i at the beginning of the contest and it uses bib_i of charge per minute (i.e. if the laptop has cc charge at the beginning of some minute, it becomes cbic - b_i charge at the beginning of the next minute). The whole contest lasts for kk 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 xx . 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 bib_i charge per minute then it will become bixb_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.

输入格式

The first line contains two integers nn and kk ( 1n21051 \le n \le 2 \cdot 10^5 , 1k21051 \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 nn integers a1,a2,,ana_1, a_2, \dots, a_n ( 1ai10121 \le a_i \le 10^{12} ) — the initial charge of each student's laptop.

The third line contains nn integers b1,b2,,bnb_1, b_2, \dots, b_n ( 1bi1071 \le b_i \le 10^7 ) — the power usage of each student's laptop.

输出格式

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

    2 4
    3 2
    4 2
    

    输出#1

    5
    
  • 输入#2

    1 5
    4
    2
    

    输出#2

    1
    
  • 输入#3

    1 6
    4
    2
    

    输出#3

    2
    
  • 输入#4

    2 2
    2 10
    3 15
    

    输出#4

    -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 55 :

  1. charge: [3,2][3, 2] , plug the charger into laptop 1;
  2. charge: [34+5,22]=[4,0][3 - 4 + 5, 2 - 2] = [4, 0] , plug the charger into laptop 2;
  3. charge: [44,02+5]=[0,3][4 - 4, 0 - 2 + 5] = [0, 3] , plug the charger into laptop 1;
  4. charge: [04+5,32]=[1,1][0 - 4 + 5, 3 - 2] = [1, 1] .

The contest ends after the fourth minute.

However, let's consider the charger of power 44 :

  1. charge: [3,2][3, 2] , plug the charger into laptop 1;
  2. charge: [34+4,22]=[3,0][3 - 4 + 4, 2 - 2] = [3, 0] , plug the charger into laptop 2;
  3. charge: [34,02+4]=[1,2][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.

首页