Background

In competitive matches such as table tennis, badminton, and chess, the most common format is knockout and round robin. The characteristic of the former is that there are fewer matches, each one is tense and exciting, but the randomness is higher. The latter is characterized by fairness and low chance, but the competition process is often very lengthy. The Swiss round robin system introduced in this question is named after the first chess tournament held in Switzerland in $1895$. It can be seen as a compromise between elimination and round robin matches, ensuring the stability of the competition while keeping the schedule from being too long.

Description

$2 \times N$ contestants numbered $1-2N$ will participate in the R round of the competition. Before the start of each round of competition and after all competitions, the contestants will be ranked in descending order of their total score. The total score of the contestants is the initial score before the start of the first round plus the scores of all the competitions they have participated in. If the total score is the same, the player with the smaller designated number will be ranked higher. The arrangement of each round of matches is related to the ranking before the start of the round: $1st$ and $2nd$, $3rd$ and $4th$,..., $2K-1$ and $2K$,..., $2N-1$ and $2N$, each with one match. The winner of each game gets $1$ point, and the loser gets $0$ points. That is to say, except for the first round, the arrangement of other rounds of matches cannot be determined in advance, but depends on the performance of the players in previous matches.
Given the initial score and strength value of each player, calculate the number of the player ranked $Q$-th after the $R$-round competition. We assume that the strength values of the contestants are different from each other, and the one with higher strength values always wins in each game.

Format

Input

The first line of input consists of three positive integers $N$, $R$, and $Q$, separated by a space between each two numbers, indicating that there are $2 \times N$ players, $R$ round matches, and the ranking $Q$ that we are concerned about. The second line consists of $2 \times N$ non negative integers $s1$, $s2$,..., $s2N$, separated by a space between each two numbers, where $si$ represents the initial score of the player with the number $i$. The third line consists of $2 \times N$ positive integers $w1$, $w2$,..., $w2N$, separated by a space between each two numbers, where $wi$ represents the strength value of the player with the number $i$.

Output

The output consists of only one line containing an integer, which is the number of the player ranked $Q$-th after the end of the $R$-round competition.

Samples

input1

2 4 2 
7 6 6 7
10 5 20 15

output1

1

data range

For $30\%$ of the data, $1 ≤ N ≤ 100$; For $50\%$ of the data, $1 ≤ N ≤ 10000$; For $100\%$ of the data, $1 ≤ N ≤ 100,000$，$1 ≤ R≤ 50$，$1 ≤ Q ≤ 2N$，$0 ≤ s1, s2, …, s2N ≤ 10^8$，$1 ≤ w1, w2, …, w2N ≤ 10^8$。