该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：work.in 输出文件：work.out

小明需要连续工作 $N$ 天，每天可以选择在北京或天津中的任意一地从事当日的工作（两地每天的工作内容不同）。北京的工作每日能获得的收入各不相同；同理，天津的工作每日能获得的收入也各不相同。

小明在北京和天津各有一处住所，初始状态下身处北京。往返北京与天津之间需要支付单程 $D$ 元的交通费。小明可以在每天开始工作前选择是否往返两地，进而决定当天在北京或天津工作。

请综合考虑每日工作收入与交通支出，计算小明在 $N$ 天内能够净增加的最大金额。

注：题目保证小明在这 $N$ 天内的资金足够支付交通费，不会出现因资金不足无法移动的情况。

输入格式

第一行两个整数 $N$ 和 $D$，分别表示工作总天数和北京与天津之间的单程交通费（单位：元）。

接下来 $N$ 行，第 $i$ 行两个整数 $B_i$ 和 $T_i$ 分别表示第 $i$ 天在北京和天津工作能获得的收入（单位：元）。

输出格式

输出一行一个整数，表示小明在 $N$ 天内净增加金额的最大值（单位：元）。

样例

样例 1

2 10000
20000 32000
24000 23000

45000

样例说明：

小明需工作 $2$ 天，北京与天津单程交通费为 $10000$ 元：

- 第 $1$ 天：北京工作收入 $20000$ 元，天津工作收入 $32000$ 元；

- 第 $2$ 天：北京工作收入 $24000$ 元，天津工作收入 $23000$ 元。

最优策略：

1.  第 $1$ 天从北京前往天津（花费 $10000$ 元），天津工作净收入 $32000 - 10000 = 22000$ 元；

2.  第 $2$ 天留在天津工作，净收入 $23000$ 元；

总计净增加 $22000 + 23000 = 45000$ 元。

样例 2

2 10000
42000 50000
58000 56000

100000

样例说明：

最优策略：全程不移动，$2$ 天都在北京工作，总收入 $42000 + 58000 = 100000$ 元（无交通支出）。

样例 3

3 10
42000 50000
58000 56000
40000 45000

152970

样例说明：

交通费仅 $10$ 元，最优策略为按「天津 → 北京 → 天津」的顺序工作，最终净增加 $152970$ 元。

数据范围

对于 30% 的数据，满足 $N \le 10$。

对于 100% 的数据，满足 $1 \le N \le 100$，$1 \le D \le 10^7$，$1 \le B_i,T_i \le 10^7$。