Maximizing the Median CSAT Score

The cows have applied to the newly founded Moo University. Each cow has a unique CSAT score (an integer between \(0\) and \(2\times10^9\)) and has requested a scholarship. The university has exactly \(N\) dormitories (\(N\) is odd) so exactly \(N\) cows must be admitted. The total scholarship budget is \(F\). The quality of the admitted class is measured by the median CSAT score (i.e. the \(\frac{N+1}{2}\)-th smallest CSAT score among the selected cows).

Your task is to select exactly \(N\) cows such that the total scholarship sum does not exceed \(F\) and the median CSAT score is maximized. It is guaranteed that every cow has a distinct score.

Note: All formulas are given in \(\LaTeX\) format. For example, the score range is \(0 \leq S \leq 2\times 10^9\) and the median is defined as the \(\frac{N+1}{2}\)-th smallest element after sorting.

inputFormat

The first line contains three integers: (N) (an odd number, the number of dormitories), (F) (the total scholarship fund), and (C) (the number of cow applicants). Each of the next (C) lines contains two integers (S) and (P), where (S) is the CSAT score of a cow and (P) is the scholarship amount that cow has requested.

outputFormat

Output a single integer representing the maximum possible median CSAT score among the admitted cows under the scholarship budget (F).

sample

3 560 4
10 100
15 500
20 50
1 10

15