給定一個長度為 $N$ 的正整數序列 $a_1, a_2, \ldots, a_N$，請你把序列切割成若干個連續段，使得……

相信身為競賽選手，諸如此類的問題肯定看過不少，為了增添趣味性，我們來做點變化：

給定一個長度為 $N$ 的正整數序列 $a_1, a_2, \ldots, a_N$，以及 $N$ 個區間 $[l_1, r_1], [l_2, r_2], \ldots, [l_N, r_N]$，請將序列切割成若干個連續段，並滿足以下條件：

• 假設序列被切成 $k$ 段，且由左數過來的第 $i$ 段的結尾為 $p_i$；也就是說，令 $p_0=0$，則由左數過來第 $i$ 個區間為 $[p_{i-1} + 1, p_{i}]$。
• 對於所有 $1\leq i\leq k$，$l_{p_{i}}\leq p_{i-1}\leq r_{p_{i}}$。

令一段被切割出來的區間 $[l, r]$ 的花費為 $\left(\max_{l\leq i\leq r} a_i\right)\times (r - l + 1)$，試問在所有合法的切割方式中，所有被切割出來的連續段的最小花費總和為何？