CodeChef - Motivation

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 (Si​,Ri​) 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 Si​ and Ri​.

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 ≤ N ≤ 5⋅104
• 1 ≤ X ≤ 109
• 1 ≤ Si​,Ri ​≤ 109 for each valid i
• X ≥ Si​ for atleast one valid i

Subtasks

Subtask #1 (100 points): original constraints

Sample 1:

Input Output

3 1
1 1 100
1 1 51
2 2
1 50
2 100
3 2
1 51
3 100
2 50

Explanation:

Example case 1: Since there is only 11 movie available and requires space equivalent to the empty space in the hard disk, Chef can only obtain maximum IMDB rating of 11.

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 33 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.

import java.util.Scanner;

class Motivation {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int T = sc.nextInt();

    while (T-- > 0) {
      int N = sc.nextInt();
      int X = sc.nextInt();

      int max = Integer.MIN_VALUE;
      while (N-- > 0) {
        int space = sc.nextInt();
        int rating = sc.nextInt();

        if (space <= X && rating > max) {
          max = rating;
        }
      }
      System.out.println(max);
    }
    sc.close();
  }
}