Problem Description

There is a chain with $N$ nodes, each having a certain weight.

For any $1 \le i \le N-1$, there is an edge connecting nodes $(i, i+1)$.

You can place some creatures on any nodes in the chain.

For the $i$-th edge, if there are at least $a_i$ creatures on node $i$ or at least $b_i$ creatures on node $i+1$, the edge can be opened.

The chain has an exit, and if there are $e$ creatures on node $1$, the exit will be opened.

You need to determine the maximum number of creatures you can place without opening the exit.

Opening the exit does not guarantee passage.

Input Format

The first line contains an integer $N$.

The second line contains an integer $e$.

The next $N-1$ lines each contain two integers $a_i$ and $b_i$.

Output Format

Output a single number, which is the maximum number of creatures you can place without escaping through the exit.

Sample Input and Output

Sample Input #1

2
20
5 5

Sample Output #1

19

Sample Input #2

2
20
5 20

Sample Output #2

24

Sample Input #3

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

Sample Output #3

23

Notes/Hints

Sample Explanation

Sample 1 Explanation

If more than $19$ creatures are placed, the exit will be opened.

Sample 2 Explanation

If we place $24$ creatures on node $2$, $4$ creatures will move to node $1$, but the exit still cannot be opened.

Sample 3 Explanation

Place $9$ creatures on node $2$ and $14$ creatures on node $7$.

Data Range and Constraints

For $100\%$ of the data, it is guaranteed that $1 \le N \le 10^3$, $1 \le e, a_i, b_i \le 10^4$.

Notes

This problem is translated from the Canadian Computing Olympiad 2018 Day 1 T3 Fun Palace.

见题面 Input 部分

见题面 Output 部分