4046 激光炮

题面

内容

Y 国有 $n$ 个实验设备从左到右摆成一排，编号依次为 $1$ 到 $n$，第 $i$ 个设备价值为 $a_i$。

W 国希望破坏 Y 国的实验设备，所以准备了 $m$ 轮激光炮轰击，第 $i$ 轮激光炮会从第 $r_i$ 个设备开始，从右到左依次轰击到第 $l_i$ 个设备，并把这些设备全部破坏。

Y 国提前知道了 W 国的计划。为了防止损失过多，Y 国准备给至多 $k$ 个设备安装能量吸收保护罩。当激光炮接触到保护罩，那个激光炮就会失效，不再继续轰击，而且被安装了保护罩的设备也不会被破坏（但是在激光炮失效之前已经轰击的设备还是会被破坏）。所以，假如一轮激光炮的轰击范围为 $[l,r]$，并在第 $x(x\in[l,r])$ 个设备上安装了能量吸收保护罩，那么激光炮的轰击范围就变成了 $[x+1,r]$。

现在你需要帮 Y 国安排在哪些设备安装保护罩，使得被破坏的设备的价值之和最小。

输入

第一行三个整数 $n,m,k$。

第二行 $n$ 个正整数依次表示 $a_{1,\dots,n}$。

接下来 $m$ 行每行两个整数表示 $l_i,r_i$。

输出

输出一个整数，表示被破坏的设备的价值之和最小值。

样例1

输入

5 3 1
3 2 3 2 1
1 5
2 3
3 3

输出

3

样例2

输入

19 8 4
1 39 28 36 19 45 21 20 32 20 22 8 3 42 29 35 26 12 16 
3 12
1 5
3 16
7 10
2 14
5 15
1 19
15 18

输出

110

提示

对于样例1：我们给设备 $3$ 安装保护罩，第二个和第三个激光在刚开始轰击时就失效，一个设备都无法破坏；第一个激光在破坏设备 $5$ 和设备 $4$ 后失效，此时破坏设备的价值和为 $3$。可以证明没有更优的方案。

对于样例2：其中一个最优解为给设备 $5,10,14,18$ 放置保护罩，其中设备 $11,12,15,16,19$ 会被破坏，价值和为 $110$。可以证明没有更优的方案。

思路

有一些从右向左扫的激光炮，假如打到了防护罩，那么这个激光炮就会失效。

对于第$i$个设备，我们定义$r_i=\min_{i\in{[l_j,r_j]}}(r_j)$，也就是能打到第$i$号点的激光炮中右端点最小的$r$，那么我们在这里放一个防护罩就一定可以保护$i$不受攻击。

而在$[i,r_i]$中选取一个$j$，那么$r_j\le{r_i}$，这是因为$r_i$是一定覆盖$j$的，若没有比这个还小的$r_j$，那么$r_j=r_i$，否则$r_j$就会比$r_i$更小。

而对于$j>r_i$，那么$r_j>r_i$，因此我们可以得出：所有的区间要么互相包含，要么无交，所以就可以根据这样的关系建一颗树：

在树上进行以点权和为标准的长链剖分，假如一条路径上放了一个防护罩，那么这条路径就是安全的，因为装置在区间的最左端，这样每次贪心地选$k$个长链就可以使保护的权值和最大，从而使破坏的权值和最小。