Description

There is a chain with $N$ nodes, and each node has a weight.

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

You may place some creatures on any nodes of the chain.

For the $i$-th edge, if node $i$ has at least $a_i$ creatures or node $i + 1$ has at least $b_i$ creatures, then this edge can be opened.

The chain has an exit. If there are $e$ creatures at node $1$, then the exit will be opened.

You need to determine the maximum number of creatures you can place, such that the creatures will not open the exit.

Opening does not necessarily mean they can pass through.

Input Format

The first line contains an integer $N$.

The second line contains an integer $e$.

The next $N - 1$ lines each contain two numbers $a_i, b_i$.

Output Format

Output a single number, the maximum number of creatures that can be placed such that the creatures will not escape through the exit.

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

Hint

Sample Explanation

Sample 1 Explanation

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

Sample 2 Explanation

Suppose we place $24$ creatures at node $2$. Then $4$ creatures will go to node $1$, but the exit still cannot be opened.

Sample 3 Explanation

Place $9$ creatures at node $2$, and place $14$ creatures at node $7$.

Constraints

For $100\%$ of the testdata, 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 Canadian Computing Olympiad 2018 Day 1 T3 Fun Palace.

Translated by ChatGPT 5