Coding Test

Coding tests have grown popular, and a company now makes problems for them and sells the problems to IT companies.

For convenience, the company divides the difficulty of its problems into levels from $0$ to $N-1$. The company currently has $A[i]$ problems rated at difficulty level $i$. It also has $B[i]$ problems rated at either level $i$ or level $i+1$, because the rating is ambiguous. No problems are rated in any other way.

The company is now looking for firms to sell problems to. A total of $M$ firms have shown interest, numbered from $0$ to $M-1$. Firm $j$ ($0 \le j \le M-1$) is only interested in problems with difficulty at least $L[j]$ and at most $U[j]$.

When selling to firm $j$, the company wants to sell one problem of each difficulty from $L[j]$ to $U[j]$ as a bundle. Call this bundle a set.

If the company sells problems only to firm $j$, what is the maximum number of sets it can sell?

A problem rated at either level $i$ or level $i+1$ can be assigned to one of the two levels, so that the number of sets sold is as large as possible. No problem may appear more than once across all the sets sold.

• $2 \le N \le 100000$
• $1 \le M \le 100000$
• $0 \le A[i] \le 10^8$ for all $0 \le i \le N-1$
• $0 \le B[i] \le 10^8$ for all $0 \le i \le N-2$
• $0 \le L[j] \le U[j] \le N-1$ for all $0 \le j \le M-1$