题目描述

有一个含 $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$。

输出格式

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

2
20
5 5

19

2
20
5 20

24

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

23

提示

样例解释

样例 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 Day 1 T3 Fun Palace。