题目描述

假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第 $i$ 个月，如果你在北京办公，你能获得 $P_i$ 的营业额，如果你在南京办公，你能获得 $N_i$ 的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付 $M$ 的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？

输入格式

输入的第一行有两个整数 $T$（$1 \le T \le 100$）和 $M$（$1 \le M \le 100$），$T$ 代表总共的月数，$M$ 代表交通费。

接下来的 $T$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的的整数，分别表示某个月在北京和在南京办公获得的营业额。

输出格式

输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。

4 3
10 9
2 8
9 5
8 2

31