Minimum Commute Cost

Alice is looking for the cheapest commuting option that does not exceed the maximum allowable travel time. You are given N commuting options. Each option is described by its travel time t and its cost c. Your task is to determine the minimum cost among all options where the travel time satisfies \( t \le M \) (in LaTeX format). If no such option exists, output -1.

More formally, given N options, for each option \( (t_i, c_i) \), find the minimum \( c_i \) such that \( t_i \le M \). If there is no \( t_i \) that satisfies \( t_i \le M \), the answer should be -1.

inputFormat

The first line of input contains two integers N and M, where:

• N (1 \(\le\) N \(\le\) 10⁵) is the number of commuting options.
• M (1 \(\le\) M \(\le\) 10⁹) is the maximum allowable travel time.

This is followed by N lines, each containing two integers. The i^th line contains t_i and c_i, representing the travel time and the cost of the i^th option respectively.

outputFormat

Output a single integer: the minimum cost among all commuting options with travel time \( t_i \le M \). If there is no valid option, output -1.

5 60
30 10
45 20
60 30
75 40
90 50

10