← 返回题目列表

Codeforces · 276/A

A. 午餐高峰

中文机器翻译题面 查看原题

写完另一场编程比赛后,三只兔子决定去吃午饭。教练给了球队正好k个时间单位的午休时间。

兔子们列出了 n 个可以去吃午饭的餐厅:第 i 个餐厅的特征是两个整数 fi 和 ti。值 ti 显示兔子需要在第 i 家餐厅吃午餐的时间。如果时间ti超过了教练规定的午休时间k,那么兔子们在这家餐厅吃午饭的快乐程度将等于fi - (ti - k)。否则,兔子会得到恰好 fi 个单位的快乐。

你的任务是找出兔子可以从午餐中获得的最大快乐值,具体取决于餐厅。兔子必须准确选择一家餐厅来吃午饭。请注意,快乐值不一定是正值。

输入

第一行包含两个空格分隔的整数 - n (1 ≤ n ≤ 104) 和 k (1 ≤ k ≤ 109) - 兔子列表中的餐厅数量以及教练给他们午餐的时间。接下来的 n 行中的每一行都包含两个以空格分隔的整数 - fi (1 ≤ fi ≤ 109) 和 ti (1 ≤ ti ≤ 109) - 第 i 家餐厅的特征。

输出

在一行中打印一个整数——兔子从午餐中获得的最大快乐值。

示例

输入 #1

2 5
3 3
4 5

输出 #1

4

输入 #2

4 6
5 8
3 6
2 3
2 2

输出 #2

3

输入 #3

1 5
1 7

输出 #3

-1