题目描述

2×N 名编号为 1∼2N 的选手共进行R 轮比赛。

每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。

选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。

总分相同的，约定编号较小的选手排名靠前。

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

第 1 名和第 2 名、第 3 名和第 4 名、……、第 2K−1 名和第 2K 名、…… 、第 2N−1 名和第2N名，各进行一场比赛。

每场比赛胜者得1分，负者得 0分。

也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第 Q 的选手编号是多少。

我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

输入

输出

样例

2 4 2 
7 6 6 7 
10 5 20 15 

1

说明

【数据范围】

对于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复赛