Contestant Ranking Simulation

There are \(2 \times N\) contestants, numbered from \(1\) to \(2 \times N\), who participate in \(R\) rounds of competitions. Before each round and after all rounds, the contestants are ranked in descending order of their total score. The total score of a contestant is defined as the sum of their initial score and all points earned in the rounds. In case of a tie in total score, the contestant with the smaller number is ranked higher.

The match-ups in each round are determined according to the current ranking: the 1st and 2nd contestants, the 3rd and 4th contestants, and so on, up to the \((2N-1)\)th and \(2N\)th contestants. In every match, the winner earns \(1\) point while the loser earns \(0\) points. Except for the first round (where the initial scores determine the ranking), the match-ups in subsequent rounds depend on the performances in previous rounds.

All contestants have distinct skill levels and in every match the contestant with the higher skill always wins. Given the initial scores and skills of each contestant, your task is to determine the number assigned to the contestant who is ranked \(Q\) after \(R\) rounds of competitions.

inputFormat

The first line of input contains three integers: \(N\), \(R\), and \(Q\).

This is followed by \(2 \times N\) lines. Each of these lines contains two integers representing a contestant's initial score and skill. The contestants are given in order from contestant \(1\) to contestant \(2 \times N\).

outputFormat

Output a single integer: the number of the contestant who occupies the \(Q\)th rank after \(R\) rounds of competitions.

sample

2 3 2
3 1
1 2
4 3
2 4

4