P6715 [CCO 2018] Fun Palace

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.**

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 a single number, the maximum number of creatures that can be placed such that the creatures will not escape through the exit.

#### 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 | Subtask ID | Points | Special Constraints | | :-: | :-: | :-: | | 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$ | None | 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](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. Translated by ChatGPT 5