There are n coders looking for a job, and you want to hire m of them to your team. For each coder, quality q and salary s is given. No two coders have the same quality. In addition, you can use at most c amount of money for the salaries.

Your task is to select the coders so that the median (i.e., the middle value in a sorted list of values) of the qualities is as large as possible.

Input

The first input line contains three integers: n, m and c. After this, there are n lines. Each line describes one coder and contains values q and s.

Output

Output one integer: the maximum median quality of the team. If you can't hire any team, output QAQ.

Constraints

• 1 \le n \le 10^5
• 1 \le m \le n, m is odd
• 1 \le c \le 10^9
• 1 \le q \le 10^9
• 1 \le s \le 10^9

Example

Input:

5 3 100
10 60
7 25
4 30
1 20
6 40

Output:

6

In this case, one solution is to hire the coders with qualities 4, 6 and 7. Their total salary 95 doesn't exceed 100.