题目背景

“你能爱我三天吗？”

“哪三天？”

“今天，明天......”

“和每一天。”

题目描述

小 $\zeta$ 在给学弟出校内模拟赛的签到题时，因为出不出来一道送分的可爱签到题沉沉睡去，他梦到了这么一道题：

有长度为 $n$ 的序列 $a,b$，对于 $1 \le i \le n$，$a_i$ 的值给定，$b_i$ 初始时均为 $0$。你需要支持以下操作 $m$ 次：

• l r v 表示先算出 $v'=v(1-\max_{i=l}^r|b_i|)$，对于 $l \le i \le r$，$b_i \leftarrow b_i+v'$。

$m$ 次操作后你需要输出 $\sum_{i=1}^na_ib_i$。

他感觉这道题很有意思，于是下载了这道题的数据包并查看，但是，因为早六的起床铃声，他忘记了每次操作分别的 $v$ 值和操作的相对顺序，但是他知道，且每次操作的 $v$ 值都满足 $v\in\{-1,1\}$。

他决定找到一种还原这道题数据并加以适当的修改的方法使得最后输出的答案最大。修改是关于这道题目中操作的区间范围的，他允许自己进行最多 $k$ 次如下操作：

• 选定 $1 \le i \le m$，进行 $l_i \leftarrow l_i-1$、$l_i \leftarrow l_i+1$、$r_i \leftarrow r_i-1$、$r_i \leftarrow r_i+1$ 四种操作中的一种。且始终保证 $1 \le l_i \le r_i \le n$。

请你求出按照以上要求还原并修改这道题数据的方案中，最大的输出答案。

为了方便你完成这个任务，小 $\zeta$ 贴心的告诉你了一个很有用的性质：所有给出的操作区间在还原前互不严格包含（即不存在 $1 \le i,j \le m$ 使得 $l_i<l_j\le r_j<r_i$），当然你在修改后可以破坏掉它。

输入格式

第一行输入三个空格分隔的整数 $n,m,k$，分别表示序列长度、操作次数和修改次数。

第二行输入 $n$ 个空格分隔的整数，第 $i$ 个是 $a_i$。

接下来 $m$ 行，其中的第 $i$ 行输入两个空格分隔的整数 $l_i,r_i$，表示第 $i$ 个操作区间。

输出格式

一行一个整数，为最大的输出答案。

5 2 2
1 2 -3 -4 5
1 1
2 3

8

5 2 3
1 2 -3 -4 5
1 1
2 3

10

10 4 5
2 2 -3 -4 -5 1 2 -10 -9 -5
2 3
2 5
1 2
6 7

38

10 4 6
2 2 -3 -4 -5 1 2 -10 -9 -5
2 3
2 5
1 2
6 7

40

10 4 1000
2 2 -3 -4 -5 1 2 -10 -9 -5
2 3
2 5
1 2
6 7

43

提示

【样例解释 #1】

• 把区间 $[2,3]$ 移动到 $[3,4]$，消耗 $2$ 次修改次数；
• 按照参数组 $(3,4,-1),(1,1,1)$ 的顺序操作，答案最大值为 $8$。

【样例解释 #3】

• 把区间 $[2,5]$ 移动到 $[3,5]$，消耗 $1$ 次修改次数。
• 把区间 $[6,7]$ 移动到 $[7,10]$，消耗 $4$ 次修改次数。
• 按照参数组 $(3,5,-1),(2,3,1),(1,2,1),(7,10,-1)$ 的顺序操作，答案最大值为 $38$。

【数据规模与约定】

本题采用捆绑测试。

子任务编号	$n \le$	$m \le$	$k \le$	分值
$0$	$10$	$5$		$10$
$1$	$10^3$	$100$	$1$	$15$*
$2$	$20$	$5$	$20$	$15$
$3$	$100$	$10$	$100$	$30$
$4$	$10^3$	$100$	$10^3$

*：子任务 $1$ 测点等分加和，其中存在 $5$ 分的测试点满足 $k=0$。

对于所有数据，$1 \le n \le 1000$，$1 \le m \le 100$，$0 \le k \le 1000$，$0 \le |a_i| \le 10^6$，对任意 $1 \le i \le m$ 有 $1 \le l_i \le r_i \le n$，不存在 $\boldsymbol{ 1 \le i,j \le m }$ 使得 $\boldsymbol{ l_i<l_j\le r_j<r_i }$。