你正在努力为你的朋友们筹备一场有趣的派对。幸运的是，你刚刚找到了举办这场派对的完美场所：一座“趣味宫殿”。这座趣味宫殿有 $N$ 个趣味房间，呈线性结构排列。趣味房间编号为 $1$ 到 $N$，对于 $1 \le i \le N - 1$，趣味房间 $i$ 和 $i + 1$ 之间由一条“趣味隧道”连接。我们称这条趣味隧道关联着趣味房间 $i$ 和 $i + 1$。此外，趣味房间 $1$ 还关联着一条离开趣味宫殿的“出口隧道”。

趣味隧道有两种状态：开启或关闭。当房间 $i$ 和 $i + 1$ 之间的趣味隧道开启时，朋友们可以在两个房间之间自由往来。

默认情况下，所有趣味隧道都是关闭的。然而，它们可以由一组朋友按下所需数量的“趣味按钮”来暂时开启。对于每条趣味隧道，在与该隧道相连的趣味房间中都设有一组趣味按钮。如果与隧道相连的其中一个房间内的所有按钮都被不同的朋友按下，那么该趣味隧道就会开启。否则，趣味隧道会立即关闭。房间 $i$ 和 $i + 1$ 之间的趣味隧道连接着房间 $i$ 中的 $a_i$ 个按钮和房间 $i + 1$ 中的 $b_i$ 个按钮。换句话说，如果房间 $i$ 中至少有 $a_i$ 个朋友，或者房间 $i + 1$ 中至少有 $b_i$ 个朋友，那么房间 $i$ 和 $i + 1$ 之间的隧道就可以开启。

出口隧道遵循类似的规则，但它仅连接到房间 $1$ 中的一组 $e$ 个按钮。

你希望确保你的朋友们获得最大的乐趣，而这显然意味着要让你的朋友们永远被困在趣味宫殿里。在出口隧道永远不会开启的前提下，你可以分配到各个趣味房间的朋友的最大总数是多少？

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示趣味房间的数量。 第二行包含一个整数 $e$ ($1 \le e \le 10\,000$)。 接下来的 $N - 1$ 行，每行包含两个空格分隔的整数，其中第 $i$ 行包含 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10\,000$)。

对于 $25$ 分中的 $3$ 分，满足 $1 \le e \le 200, a_i = 1, b_i = 1$。 对于另外 $25$ 分中的 $5$ 分，满足 $1 \le e, a_i, b_i \le 2$。 对于另外 $25$ 分中的 $12$ 分，满足 $N \le 200, 1 \le e, a_i, b_i \le 200$。

输出格式

输出一个整数，表示在所有可能的分配方案下，使得朋友们无法开启出口隧道的前提下，朋友们的最大总数。

样例

样例输入 1

2
20
5 5

样例输出 1

19

说明 1

如果我们有超过 $19$ 个朋友，他们将能够移动到房间 $1$ 并按下开启出口隧道所需的全部 $20$ 个按钮。

样例输入 2

2
20
5 20

样例输出 2

24

说明 2

假设我们将 $24$ 个朋友放在房间 $2$。为了开启房间 $1$ 和 $2$ 之间的隧道，必须有 $20$ 个朋友留在房间 $2$ 以按下趣味按钮。这使得只有 $4$ 个朋友能进入房间 $1$，这不足以按下房间 $1$ 中那组 $5$ 个按钮中的全部。

样例输入 3

7
7
2 8
6 6
1 1
2 4
2 8
7 8

样例输出 3

23

说明 3

一种最优的分配方案是将 $9$ 个朋友放在房间 $2$，将 $14$ 个朋友放在房间 $7$。