题目描述

译自 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）。

样例 1

input

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

output

39
2 6
2 4

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

样例 2

input

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

output

34
0 0
1 3

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

样例 3

input

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

output

19
1 1
3 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.$