学习轨迹

题号：NC53311
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

译自 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。
第二行：。
第三行：。
第四行：。
第五行：。

输出描述:

第一行：r。
第二行：（如果神犇不打算在清华听课，请输出00）。
第三行：（如果神犇不打算在北大听课，请输出00）。

示例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

输出

复制

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

输入

复制

输出

复制

34
0 0
1 3

说明

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

示例3

输入

复制

输出

复制

19
1 1
3 3

备注:

对于所有数据，

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2773