Lunch Choice
While furiously programming the donation site for the Cameron Hall 2020 Charity UnVigil (https://charityunvigil.online/) James and Felix decide to have a lunch break. Being extremely hard workers they give themselves exactly \(k\) units of time to have lunch.
They have a list of \(n\) venues. The \(i\)-th venue is characterized by two integers \(f_i\) and \(t_i\). \(t_i\) is the time needed to lunch at the \(i\)-th venue. If \(t_i\) exceeds \(k\) then James and Felix's joy will equal \(f_i - (t_i - k)\). Otherwise they get exactly \(f_i\) units of joy.
Your task as the omniscient narrator is to choose the best place to have lunch maximizing joy (which may not be positive).
Input Specification
The first line contains two space-separated integers \(n (1 \leq n \leq 10^4)\) and \(k(1 \leq k \leq 10^9)\); the number of venues and time they give themselves respectively. Each of the next \(n\) lines contains two space-separated integers \(f_i (1 \leq f_i \leq 10^9)\) and \(t_i (1 \leq t_i \leq 10^9)\), the characteristics of the \(i\)-th venue.
Output Specification
A single integer, the maximum joy that James and Felix can get from their lunch.
Sample Input 1
2 5
3 3
4 5
Sample Output 1
4
Sample Input 2
4 6
5 8
3 6
2 3
2 2
Sample Output 2
3
Sample Input 3
1 5
1 7
Sample Output 3
-1
Comments