200297 - 音游3

音游有若干关,通过第i关得到k_i个音符石,开启第i关需要使用m_i个音符石。小j同学经过夜以继日的努力,所有关卡都能一次通过,于是获得了大师通行卡。大师通行卡可以让小j同学任意选择关卡顺序进行游戏。现在小j同学打算炫技,炫技前小j现在有k个音符石,炫技结束后小j最多能有多少个音符石?

输入

第一行,有单个空格分隔的两个整数n,k,分别表示关卡个数和初始的音符石个数。

接下来n行,每行有单个空格分隔的两个整数k_i,m_i分别表示通关第i关得到的音符石个数和开启第i关需要的音符石个数。

对于100%的数据:

0\le n,k \le 10^5

0\le k_i,m_i \le 10^9

输出

一个正整数,表示炫技结束后,小j共有多少个音符石。

样例

输入

3 5
4 3
4 3
4 3

输出

8

输入

2 1
5 2
8 2

输出

1

输入

2 6
2 3
4 3

输出

7
时间限制 1000 毫秒
内存限制 128 MB
统计
上一题 下一题