Description

There are 2N players numbered from 1 to 2N who compete in R rounds of matches. Before each round begins and after all matches conclude, the players are ranked once based on their total scores in descending order. A player's total score is the sum of their initial score before the first round and all points earned from the matches they have participated in. If two players have the same total score, the one with the smaller ID is ranked higher.

The match arrangement for each round is determined by the current ranking before that round: the 1st-ranked player faces the 2nd-ranked, the 3rd-ranked faces the 4th-ranked, ..., the (2K-1)-th-ranked faces the (2K)-th-ranked, ..., and the (2N-1)-th-ranked faces the (2N)-th-ranked in each match. The winner of each match earns 1 point, while the loser earns 0 points. This means that except for the first round, the arrangements for subsequent rounds cannot be predetermined but depend on the players' performances in prior matches.

Given each player's initial score and their strength value, calculate the ID of the player ranked Q-th after R rounds of matches. It is assumed that all players have distinct strength values, and the player with the higher strength value always wins in any match.

Input Format

The input consists of three lines:

• The first line contains three positive integers N, R, and Q, separated by spaces, representing the number of players (2*N), the number of rounds (R), and the rank of interest (Q).
• The second line contains 2*N non-negative integers s1, s2, ..., s2N, separated by spaces, where si denotes the initial score of the player with ID i.
• The third line contains 2*N positive integers w1, w2, ..., w2N, separated by spaces, where wi denotes the strength value of the player with ID i.

Output Format

The output consists of a single line containing an integer, which is the ID of the player ranked Q-th after R rounds of matches.

2 4 2
7 6 6 7
10 5 20 15

1

Source

NOIP2003-J3

(Note: NOIP stands for National Olympiad in Informatics in Provinces, which is a Chinese programming competition for secondary school students. The "J3" likely indicates this is the third problem in the junior division of the 2003 contest.)