#[2773].「ROI 2017 Day 2」学习轨迹

内存限制：512 MB 时间限制：2000 ms

译自 ROI 2017 Day 2 T4. Траектория обучения

T 大和 P 大同时向一位神犇抛出了橄榄枝。
清华有 $n$ 门课程，课程的编号分别为 $a_1\dots a_n$（注意不是 $1\ldots n$），$i$ 号课程的质量为 $x_i$。北大有 $m$ 门课程，课程的编号分别为 $b_1\dots b_m$，$i$ 号课程的质量为 $y_i$。清华和北大开设的课程可能相同（即编号相同），学校内部不会开设两门编号相同的课。
神犇可以在清华学习课程 $l_a\sim r_a$ $(1⩽ l_a⩽ r_a⩽ n)$，也可以不去清华。同时，神犇可以在北大学习课程 $l_b\sim r_b$ $(1⩽ l_b⩽ r_b⩽ m)$，也可以不去北大。神犇太强了，他可以两所学校都去。
神犇不想把时间浪费在同样的课程上。因此，神犇不会选择两门相同的课程。
试求：神犇能听到的课程的质量总和的最大值 $r$。

第一行：$n,m$。
第二行：$a_1\dots a_n$。
第三行：$x_1\dots x_n$。
第四行：$b_1\dots b_m$。
第五行：$y_1\dots y_m$。

第一行：$r$。
第二行：$l_a, r_a$（如果神犇不打算在清华听课，请输出 0 0）。
第三行：$l_b, r_b$（如果神犇不打算在北大听课，请输出 0 0）。

最优解如样例所示，课程质量之和为 $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39.$ 次优解：$(7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38.$

由于北大的 $1$ 号、$2$ 号课程相比清华的相同课程的质量要高得多，因此最优解是拒掉清华，转而在北大读 $1\sim 3$ 号课程。

对于所有数据，$1 ⩽ n, m ⩽ 5\times 10^5,1⩽ a_i,b_i⩽ n+m,$ $a_i≠a_j,$ $b_i≠b_j,$ $1⩽ x_i,y_i⩽ 10^9.$

子任务编号	分值	$n,m ⩽$	子任务编号	分值	$n,m ⩽$
1	10	$50$	6	5	$5000$
2	10	$100$	7	5	$10^4$
3	10	$300$	8	10	$3\times 10^4$
4	10	$500$	9	10	$10^5$
5	10	$2000$	10	10	$2.5\times 10^5$
			11	10	$5\times 10^5$

样例输入 1

7 5
3 1 4 8 6 9 2
2 7 4 10 1 5 3
9 2 11 3 8
3 5 3 4 12

样例输出 1

39
2 6
2 4

样例输入 2

样例输出 2

34
0 0
1 3

样例输入 3

样例输出 3

19
1 1
3 3

2773 「ROI 2017 Day 2」学习轨迹

题目描述

输入格式

输出格式

样例 1

样例 2

样例 3

数据范围与提示