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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 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⩽ n) ,也可以不去北大。神犇太强了,他可以两所学校都去。
神犇不想把时间浪费在同样的课程上。因此,神犇不会选择两门相同的课程。
试求:神犇能听到的课程的质量总和的最大值 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)。

样例

样例输入 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

样例说明 1

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

样例输入 2

2 3
1 2
1 4
2 3 1
17 2 15

样例输出 2

34
0 0
1 3

样例说明 2

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

样例输入 3

3 3
4 2 1
10 1 2
5 4 2
1 2 9

样例输出 3

19
1 1
3 3

数据范围与提示

对于所有数据, 1 ⩽ n, m ⩽ 5\times 10^5,1⩽ a_i,b_i⩽ n+m,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