← 返回题目列表

AtCoder · icpc2015summer_day3_h

H. 残疾人现场预测

中文机器翻译题面 查看原题

AtCoder镜像页只保留了来源名称;以下原题页取自作品原始英文题册,现已完整保存到本地。

Handicapped Onsite Prediction - 原题 PDF
赛事原始英文题册页面
可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
                   Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem H. Handicapped Onsite Prediction

    Input   le:        hop.in
    Output   le:       hop.out
    Time limit:        2 seconds
   Memory limit:     256 megabytes

Do you think that winning a competition is easy? This is not the case when there are so many
incredible competitors around.

You're taking part in the OpenBowl programming contest. It consists of two rounds    online
round and onsite round. Besides you, there are N −1 more competitors eager to win. Each of
N competitors has already taken part in the online round, and competitor i received exactly Ai
points (you have no idea about how these numbers were calculated   only Sn., the main contest
organizer, knows everything about that; you've only heard that it had something to do with
conditionally unrated rounds).

Now it's time for the onsite round. At the onsite round every competitor takes some place between
1 and N, inclusive, and no two contestants take the same place. For place j at the onsite round Pj
points are awarded, and the  nal score of the contestant is equal to the sum of points received by
him during the online and the onsite rounds. Then each competitor's  nal place is calculated
for competitor i it is equal to k + 1, where k is the number of competitors whose  nal score is
strictly greater than that of competitor i.

You clearly understand that your rivals are very strong. That's why you aren't even aiming at
winning the contest. You decided that you will be pleased with your result if the  nal place you
take is not lower than X. Now you would like to  nd out: what is the lowest place at the onsite
round you should take to guarantee that?

Input

The input  le contains two integer numbers N and X (1 ≤X ≤N ≤105), followed by N integer
numbers Ai   the number of points competitor i received during the online round, followed by N
integer numbers Pj   the number of points received by the competitor who takes place j at the
onsite round (0 ≤Ai, Pj ≤109). It is guaranteed that Pj ≥Pj+1 for any j, 1 ≤j < N. You are
competitor number 1.

Output

Output one integer number between 1 and N, inclusive   the lowest place at the onsite round
you should take in order to guarantee taking place X or higher overall, or −1 if it is impossible
to have such a guarantee even in case of winning the onsite round.

Examples

               hop.in                              hop.out
 5 3                                  2
 230 310 200 260 180
 100 80 60 50 45
 5 2                                  -1
 230 310 200 260 180
 100 80 60 50 45


                                     Page 8 of 10