T2 大富翁

题目描述

新生们为了促进感情，准备去玩桌游，他们选择了大富翁游戏。大富翁的胜利目标是为了收取更多的租金，获得更多的钱。

地图上有 $n$ 栋房屋，一开始并不会产出租金。

每栋房屋都可以被“购买”一次，也可以被“装修”一次（需要在购买之后）。如果一栋房屋被“购买”，则这栋房屋每天可以产生一个金币的租金，如果一栋房屋被“购买”且“装修”，则这栋房屋每天可以产生两个金币的租金。

购买房屋和装修房屋都与要一定时间，第 $i$ 房屋被购买需要 $a_{i,0}$ 时间，被装修需要 $a_{i,1}$ 时间。一个人在同一时间只能进行一个操作，也就是说不可以同时对两个房屋进行操作，也不可以同时购买或装修一个房屋。不同房屋之间没有时间顺序的限制，一个人可以从任意一个房屋开始购买，且可以任意切换房屋进行购买或装修。

zzy 想知道他到第 $m$ 时刻结束时最多能获得多少金币。由于新生想更好的促进感情，所以他们会玩很长时间，保证 $m \ge 10^{10}$

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行两个整数 $a_{i,0},a_{i,1}$。

输出格式

一行一个整数，代表 zzy 能获得多少钱。

样例输入 #1

2 10000000000
2 1
1 2

样例输出 #1

39999999986

数据范围与约定

对于所有数据，有：

• $10^{10} \le m \le 10^{11}$

• $n \le 6 \times10^5$

• $0 \le a_{i,j} \le 5\times10^3$