Description

There are 2*N players numbered from 1 to 2*N who compete in R rounds of matches. Before each round begins and after all matches conclude, the players are ranked 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 matches played so far. If two players have the same total score, the one with the smaller ID is ranked higher.

The match pairings for each round are 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. Each match awards the winner 1 point and the loser 0 points. This means that except for the first round, the pairings for subsequent rounds cannot be predetermined and depend on the players' performances in prior matches.

Given the initial scores and strength values of each player, 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 stronger player always wins a match.

Input Format

The first line of input contains three positive integers N, R, and Q, separated by single spaces, representing the number of player pairs (2*N players), 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 single 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 single 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.

```input1 2 4 2 7 6 6 7 10 5 20 15 ``` ```output1 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.)