30365번 - Disjoint-Sparse-Table Optimization 다국어

문제

You are given an integer sequence $A$ of length 2ドルQ-1$ and $Q$ intervals $[L_i, R_i)$. Here, $L_i,ドル $R_i$ satisfy $L_i < R_i,ドル and each integer between 1ドル$ and 2ドルQ$ 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, \dots, 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} + \dots + A_{r-1}$ for all intervals $[l,r)$ included in $S$.

Find the minimum cost of the set that satisfies the condition.

입력

$Q$

$L_1$ $R_1$

$\vdots$

$L_Q$ $R_Q$

$A_1$ $A_2$ $\dots$ $A_{2Q-1}$

출력

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

제한

• All inputs consist of integers.
• 1ドル \le Q \le 100$
• 1ドル \le L_i < R_i \le 2Q$
• Each integer from 1ドル$ to 2ドルQ$ appears in $L_1, \dots, L_Q, R_1, \dots, R_Q$.
• 1ドル \le A_i \le 10^9$

힌트

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