李老头（李 * 城）以推拿称霸江湖，所以小Q慕名而来放松身心。
李老头可以推拿 个穴位，每个穴位一个人一天只能推拿一次，对于第 个穴位，可以让小Q放松 点，需要 个老登币（老登国专用货币），小Q带了 个老登币，请你帮他算算，他最多能放松多少个点。
第一行两个正整数，分别是 和 。 接下来 行，每行两个正整数，分别是 和 。
仅有一行，输出答案。
样例输入 1
3 3 3 2 1 1 2 1
样例输出 1
5
样例输入 2
5 10 2 4 5 9 3 5 5 7 4 3
样例输出 2
9
保证输出答案小于 。