Maximizing Creature Placement without Triggering the Exit

You are given a chain of N nodes (indexed from 1 to N), each with a capacity (weight) w_i. For each consecutive pair of nodes there is an edge between node i and node i+1 (for 1 ≤ i ≤ N-1). You may place a nonnegative integer number of creatures on each node – however, on node i you cannot place more than w_i creatures.

There are additional rules about edge opening. For the i-th edge (connecting nodes i and i+1), an edge can open if either of the following holds: $$x_i \geq a_i \quad \text{or} \quad x_{i+1} \geq b_i, $$

where x_i is the number of creatures placed on node i, and the parameters a_i and b_i are given.

The chain has an exit. If node 1 ends up with exactly e creatures, the exit will be opened. In a worst‐case scenario, if some edges are open, creatures from nodes that are connected to node 1 might eventually all move to node 1. In other words, if the connected component (via open edges) containing node 1 eventually accumulates a total of at least e creatures (with node 1 included) then the exit will open. (Note that an open edge does not necessarily mean that creatures will move across it, but you must assume the worst‐case possibility.)

Your task is to determine the maximum total number of creatures you can place on the chain without triggering the exit – that is, so that even if every open edge allows all connected creatures to move to node 1, the number of creatures arriving there is strictly less than e.

You may choose, for each edge, whether it becomes open or remains closed by controlling the numbers on its endpoints. In particular, if you wish to isolate node 1 from the rest of the chain, you can guarantee that an edge remains closed by ensuring that both endpoints fall below the respective thresholds (x_i < a_i and x_i+1 < b_i). Nodes that are not connected (directly or indirectly) to node 1 can be fully saturated with creatures (i.e. set to their maximum capacity w_i) without risk. However, if you choose to connect some nodes with node 1 (by allowing an edge to open), then the total creatures placed in that connected block (which includes node 1) must be less than e because, in the worst case, they can all end up at node 1.

Input summary:

• An integer N and an integer e.
• A line of N integers denoting the capacities (weights) w₁, w₂, …, w_N.
• N-1 lines follow, each with two integers: a_i and b_i for edge i (connecting nodes i and i+1).

Output summary:

Print the maximum total number of creatures that can be placed without ever risking the exit to be triggered.

Note: You must devise an allocation strategy that, for some prefix of nodes connected to node 1 via open edges, ensures that the sum of creatures in that connected block is less than e. For nodes outside that block (separated by a deliberately closed edge) you may assign the full capacities.

Constraints (assumed small): You may assume that all numbers (N, e, w_i, a_i, b_i) are positive integers and are small enough to allow a dynamic programming solution.

inputFormat

The first line contains two integers N and e — the number of nodes and the exit threshold for node 1 respectively.

The second line contains N integers: w₁, w₂, …, w_N, where w_i is the capacity of node i.

Then follow N-1 lines. The i-th of these lines contains two integers: a_i and b_i, which are the thresholds for the i-th edge connecting node i and node i+1.

outputFormat

Output a single integer – the maximum total number of creatures that can be placed on the chain without triggering the exit.

sample

3 10
5 5 5
3 4
2 6

10