2×N 名编号为 1∼2N 的选手共进行R 轮比赛。 每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。 选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。 总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关： 

第 1 名和第 2 名、第 3 名和第 4 名、……、第 2K−1 名和第 2K 名、…… 、第 2N−1 名和第2N名，各进行一场比赛。 每场比赛胜者得1分，负者得 0分。

也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第 Q 的选手编号是多少。 我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

第一行是三个正整数 $N,R,Q$每两个数之间用一个空格隔开，表示有 2×N 名选手、R轮比赛，以及我们关心的名次 $Q$。

第二行是 $2N$ 个非负整数，每两个数之间用一个空格隔开，其表示编号为 i 的选手的初始分数。

第三行是 $2N$ 个正整数，每两个数之间用一个空格隔开，其表示编号为 i 的选手的实力值。

一个整数，即 R 轮比赛结束后，排名第Q 名的选手的编号。

【数据范围】

对于30%的数据，1 ≤ N ≤ 100；

对于50%的数据，1 ≤ N ≤ 10,000；

对于100%的数据，1 ≤ N ≤ 100,000,1 ≤ R ≤ 50,1 ≤ Q ≤ 2N,0 ≤ _s1,_s2, …, _s2N≤10⁸,1 ≤_W1, _W2 , …, _W2N≤ 10⁸

noip2011普及组第3题。

来源

noip复赛

noip复赛