{"problem":{"name":"[ROI 2017] 学习轨迹 (Day 2)","description":{"content":"THU 和 PKU 同时开设了一批课程，THU 有 $n$ 节课，PKU 有 $m$ 节课。 其中 THU 第 $i$ 节课类别是 $a_i$，乐趣度是 $x_i$；PKU 第 $i$ 节课类别是 $b_i$，乐趣度是 $y_i$。保证 $a$ 中元素互不相同，$b$ 中元素互不相同，但是 $a$ 和 $b$ 之间可能有相同元素。 你可以选择听 THU 的 $l_1 \\sim r_1$ 节课，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10656"},"statements":[{"statement_type":"Markdown","content":"THU 和 PKU 同时开设了一批课程，THU 有 $n$ 节课，PKU 有 $m$ 节课。\n\n其中 THU 第 $i$ 节课类别是 $a_i$，乐趣度是 $x_i$；PKU 第 $i$ 节课类别是 $b_i$，乐趣度是 $y_i$。保证 $a$ 中元素互不相同，$b$ 中元素互不相同，但是 $a$ 和 $b$ 之间可能有相同元素。\n\n你可以选择听 THU 的 $l_1 \\sim r_1$ 节课，收获到的乐趣度为所有你听的课的乐趣度的和；同时可以在 PKU 听 $l_2 \\sim r_2$ 节课，收获到的乐趣度也是所有你听的课的乐趣度的和。（当然你也可以选择只听一所大学的课甚至不听）\n\n同一类别的课你不能听两次，也就是如果 $a_{l_1 \\sim r_1}$ 中有元素与 $b_{l_2 \\sim r_2}$ 相同，那么这个听课方案就不能满足你的胃口。\n\n你需要求出可能的听课方案中乐趣度最大的是多少以及具体的安排。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n接下来四行，每行一个整数序列，分别表示题目中的 $a,x,b,y$，这四个序列长度分别为 $n,n,m,m$。\n\n## Output\n\n第一行一个整数表示最大乐趣度。\n\n第二行两个整数 $l_1,r_1$，如果你不打算在 THU 听课，输出 `0 0`。\n\n第三行两个整数 $l_2,r_2$，如果你不打算在 PKU 听课，输出 `0 0`。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n对于样例组 #1：\n\n最优解如样例所示，课程质量之和为 $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$。\n\n对于样例组 #2：\n\n由于 PKU 的 $1$ 号、$2$ 号课程相比 THU 的相同课程的质量要高得多，因此最优解是不去 THU 听课，转而在 PKU 读 $1\\sim 3$ 号课程。\n\n#### 【数据范围】\n\n注：本题只放部分数据，完整数据请左转 [LOJ P2773](https://loj.ac/p/2773) 评测。\n\n对于所有数据满足：$1 \\le a_i,b_i \\le n+m$，$1 \\le x_i,y_i \\le 10^9$，$a_i \\ne a_j(i \\ne j)$，$b_i \\ne b_j(i \\ne j)$。\n\n| 子任务编号 | 分值 | $1 \\le n,m \\le $ |\n| :----------: | :----------: | :----------: |\n| $1$ | $10$ | $50$ |\n| $2$ | $10$ | $100$ |\n| $3$ | $10$ | $300$ |\n| $4$ | $10$ | $500$ |\n| $5$ | $10$ | $2000$ |\n| $6$ | $5$ | $5000$ |\n| $7$ | $5$ | $10^4$ |\n| $8$ | $10$ | $3 \\times 10^4$ |\n| $9$ | $10$ | $10^5$ |\n| $10$ | $10$ | $2.5 \\times 10^5$ |\n| $11$ | $10$ | $5 \\times 10^5$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10656","tags":["动态规划 DP","贪心","2017","线段树","Special Judge","O2优化","ROI（俄罗斯）"],"sample_group":[["7 5\n3 1 4 8 6 9 2\n2 7 4 10 1 5 3\n9 2 11 3 8\n3 5 3 4 12","39\n2 6\n2 4"],["2 3\n1 2\n1 4\n2 3 1\n17 2 15","34\n0 0\n1 3"],["3 3\n4 2 1\n10 1 2\n5 4 2\n1 2 9","19\n1 1\n3 3"]],"created_at":"2026-03-03 11:09:25"}}