7225: CodeChef IMDB - Motivation
[Creator : ]
Description
Chef has been searching for a good motivational movie that he can watch during his exam time.
His hard disk has $X$ GB of space remaining. His friend has $N$ movies represented with $(S_i, R_i)$ representing (space required, IMDB rating). Help Chef choose the single best movie (highest IMDB rating) that can fit in his hard disk.
His hard disk has $X$ GB of space remaining. His friend has $N$ movies represented with $(S_i, R_i)$ representing (space required, IMDB rating). Help Chef choose the single best movie (highest IMDB rating) that can fit in his hard disk.
Input
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers N and X.
N lines follow. For each valid i, the i-th of these lines contains two space-separated integers $S_i$ and $R_i$.
The first line of each test case contains two space-separated integers N and X.
N lines follow. For each valid i, the i-th of these lines contains two space-separated integers $S_i$ and $R_i$.
Output
For each test case, print a single line containing one integer - the highest rating of an IMDB movie which Chef can store in his hard disk.
Constraints
$1≤T≤10$
$1 \leq N \leq 5 \cdot 10^4$
$1 \leq X \leq 10^9$
$1 \leq S_i, R_i \leq 10^9$ for each valid i
$X \ge S_i$ for atleast one valid i
$1 \leq N \leq 5 \cdot 10^4$
$1 \leq X \leq 10^9$
$1 \leq S_i, R_i \leq 10^9$ for each valid i
$X \ge S_i$ for atleast one valid i
Sample 1 Input
3
1 1
1 1
2 2
1 50
2 100
3 2
1 51
3 100
2 50
Sample 1 Output
1
100
51
Example case 1: Since there is only 1 movie available and requires space equivalent to the empty space in the hard disk, Chef can only obtain maximum IMDB rating of 1.
Example case 2: Since out of the 2 available movies, both can fit in the free memory, we only care to take the one with higher rating, i.e, rating of max(50, 100) = 100.
Example case 3: Since out of the 3 available movies, only the first and the last movies fit in the free memory, we only care to take the one with higher rating amongst these 2, i.e, rating of max(51,50)=51.
Example case 2: Since out of the 2 available movies, both can fit in the free memory, we only care to take the one with higher rating, i.e, rating of max(50, 100) = 100.
Example case 3: Since out of the 3 available movies, only the first and the last movies fit in the free memory, we only care to take the one with higher rating amongst these 2, i.e, rating of max(51,50)=51.