#P13776. 【PR #16】Cheating Plan

    ID: 12972 传统题 1000ms 1024MiB 尝试: 53 已通过: 7 难度: 6 上传者: 标签>CF2100提高消除被支配候选自定义排序规则二分查找懒标记线段树扫描中维护贡献

【PR #16】Cheating Plan

题目描述

小 L 正在参加一年一度的算法竞赛盛会 SXCPC!

今年的比赛中一共有 KK 道题目。小 L 与他的队友只有 nn 分钟的时间解决它们。小 L 和队友的默契不太好,他们在比赛中甚至还会犯“思考已经通过的题目”这种低级错误!他们的做题策略是:第 ii 分钟,若编号为 aia_i 的题目当前的状态为“未通过”,他们就通过这道题。

小 L 的对手小 Y 不希望他通过太多题目,于是他贿赂了赛事主办方。赛事主办方给出了 mm 种黑幕的方案。其中第 ii 种方案的形式,是在第 t(1≤t≤n)t(1\leq t\leq n) 分钟开始前将编号包含在 [Li,Ri][L_i,R_i] 的题目全部设置为“小 L 未通过”(其中 tt 是任意的某个时间点,只能恰好选择一种黑幕方案,黑幕只能执行 恰好一次)。

令非负整数 bib_i 为第 ii 题的难度,定义 CtC_t 为在第 tt 分钟使用黑幕的情况下比赛结束后小 L 剩余状态为“未通过”的题目的 bib_i 总和,小 Y 的快乐值为 (n−t+1)×Ct(n-t+1) \times C_t。请计算小 Y 能获得的最大快乐值是多少。

输入格式

输入的第一行三个正整数 n,m,Kn,m,K 分别表示比赛时长、黑幕方案数以及比赛题目数量。

输入的第二行包含 nn 个正整数 aia_i,含义见题目描述。

输入的第三行包含 KK 个正整数 bib_i,含义见题目描述。

接下来 mm 行,每行两个正整数 Li,RiL_i,R_i,含义见题目描述。

输出格式

输出一个整数表示可获得的最大快乐值。

样例

样例输入 #1

7 6 10
4 1 2 10 1 8 2
1 1 1 1 1 1 1 1 1 1 
3 5
1 2
3 8
4 10
6 10
3 7

样例输出 #1

36

数据范围与约定

对于所有数据,有:

  • 1≤n,m,K≤1061\leq n,m,K\leq 10^6
  • 1≤ai≤K1\leq a_i\leq K
  • 0≤bi≤1060\leq b_i\leq 10^6
  • 1≤Li≤Ri≤K1\leq L_i\leq R_i\leq K

子任务:

子任务编号$n,M,K\leq$特殊性质分值
$1$$100$无$5$
$2$$1000$无$10$
$3$$10^4$无$10$
$4$$5\times 10^4$无$5$
$5$$10^5$$b_i=1$$10$
$6$$10^5$无$10$
$7$$10^6$$b_i=1$$20$
$8$$10^6$无$30$