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

可复制的 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