P6715 [CCO 2018] Fun Palace

有一个含 $N$ 个点的链，每个点有一个权值。 对于任何 $1\le i\le N-1$，都有一条边连接 $(i,i+1)$。 您可以在链中的任意一些节点放置一些生物。 对于第 $i$ 条边，若点 $i$ 至少有 $a_i$ 个生物或点 $i+1$ 至少有 $b_i$ 生物，则该边可以打开。 链是有出口的，如果在 $1$ 号点有 $e$ 个生物，则出口会被打开。 您要确定，至多放置多少个生物，可以使得生物不会打开出口。 **打开了不一定能走过去。**

第一行为一个整数 $N$。 第二行为一个整数 $e$。 接下来 $N-1$ 行，一行两个数 $a_i,b_i$。

仅一行一个数，表示至多放置多少个生物，可以使得生物不会逃出出口。

#### 样例解释 #### 样例 1 解释 如果超过 $19$ 个生物，出口就会被打开。 #### 样例 2 解释 假设我们放 $24$ 个生物在 $2$ 号点，有 $4$ 个生物就会去到 $1$ 号点，但仍然无法打开出口。 #### 样例 3 解释 $9$ 个生物放在 $2$ 号点，$14$ 个生物放在 $7$ 号点。 #### 数据范围及限制 | 子任务编号 | 分值 | 特殊限制 | | :-: | :-: | :-: | | 1 | $12$ | $1\le e\le 200$，$a_i=b_i=1$ | | 2 | $20$ | $1\le e,a_i,b_i\le 2$ | | 3 | $48$ | $1\le N,e,a_i,b_i\le 200$ | | 4 | $20$ | 无 | 对于 $100\%$ 的数据，保证 $1\le N\le 10^3$，$1\le e,a_i,b_i\le 10^4$。 #### 说明 本题译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day1.pdf) T3 Fun Palace。