John 正在玩一个手机游戏。游戏主角 Layton 需要破解 n 个关卡，开始时，Layton 有 k 点 HP 值，对于第 i 个关卡，Layton 需要花费 Ti 时间破解，如果不能破解，则会损失 1 点 HP，另外第 i 个关卡必须要在时间点 Di（游戏开始时时间点为 0）之前破解。

现在帮助 John 计算，要破解所有的关卡最少要损失的 HP 值，如果不能完成游戏，则输出-1。

第一行为正整数 t(≤5)，表示数据组数；

每组数据中，

第一行为正整数n(≤25000)和 k(≤5000)，分别表示关卡数和 Layton 最初的 HP 值；

接下来 n行，每行两个正整数 Ti(≤10^9 )和 Di(≤10^9 )，分别表示每个关卡花费的时间和限定时间。

对于每组数据，输出对应的答案。