P15717 [JAG 2023 Summer Camp #2] Disjoint-Sparse-Table Optimization

You are given an integer sequence $A$ of length $2Q - 1$ and $Q$ intervals $[L_i, R_i)$. Here, $L_i, R_i$ satisfy $L_i < R_i$, and each integer between $1$ and $2Q$ appears once as an end of an interval. Your goal is to create a set $S$ of intervals to satisfy at least one of the following conditions for all $i = 1, 2, \ldots, Q$. - $[L_i, R_i) \in S$ - There exists an integer $x$ ($L_i < x < R_i$) such that $[L_i, x) \in S$ and $[x, R_i) \in S$. The cost of the set $S$ is defined as follows. - The sum of $A_l + A_{l+1} + \ldots + A_{r-1}$ for all intervals $[l, r)$ included in $S$. Find the minimum cost of the set that satisfies the condition.

$$ \begin{aligned} &Q \\ &L_1 \ R_1 \\ &\vdots \\ &L_Q \ R_Q \\ &A_1 \ A_2 \ \ldots \ A_{2Q-1} \end{aligned} $$ The input satisfies the following constraints. - All inputs consist of integers. - $1 \leq Q \leq 100$ - $1 \leq L_i < R_i \leq 2Q$ - Each integer from $1$ to $2Q$ appears in $L_1, \ldots, L_Q, R_1, \ldots, R_Q$. - $1 \leq A_i \leq 10^9$

Output the minimum cost of the set that satisfies the condition. Add a new line at the end of the output.

In Sample Input 1, the optimal set is $S = \{[1, 4), [2, 3), [3, 5), [5, 6)\}$, where the cost is $6 + 2 + 7 + 5 = 20$.