题目描述

译自 Canadian Computing Olympiad 2018 Day 1 Fun Palace

你正为给好朋友准备一个快乐的聚会而努力着。幸运的是，你恰好选择了一个十分合适的聚会地点：快乐宫殿。快乐宫殿中有 $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$，表示房间的个数。

接下来一行包含一个整数 $e$。

接下来 $N-1$ 行，每行两个整数，第 $i$ 行包含 $a_i,b_i$。

输出格式

输出一个整数，表示最多邀请多少个朋友，使得你在给他们分配好房间之后他们永远不能打开出口管道？

样例 1

2
20
5 5

19

如果有多于 $19$ 个朋友，那么他们就可以移动到房间 $1$ 然后按下所有需要按的 $20$ 个按钮打开出口通道。

2
20
5 20

24

假设我们在房间 $2$ 安排 $24$ 个朋友。为了打开房间 $1$ 和 $2$ 之间的管道，$20$ 个朋友必须留在房间 $2$ 按着按钮。这只允许 $4$ 个朋友进入房间 $1$，并且不足以按下房间 $1$ 中集合大小为 $5$ 的每一个按钮。

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

23

一种最优分布是将 $9$ 个朋友安排到房间 $2$，将 $14$ 个朋友安排到房间 $7$。

数据范围与提示

对于全部数据，$1\le N\le 10^3,1\le e,a_i,b_i\le 10^4$。