P10656 [ROI 2017] 学习轨迹 (Day 2)

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$ 节课，收获到的乐趣度为所有你听的课的乐趣度的和；同时可以在 PKU 听 $l_2 \sim r_2$ 节课，收获到的乐趣度也是所有你听的课的乐趣度的和。（当然你也可以选择只听一所大学的课甚至不听） 同一类别的课你不能听两次，也就是如果 $a_{l_1 \sim r_1}$ 中有元素与 $b_{l_2 \sim r_2}$ 相同，那么这个听课方案就不能满足你的胃口。 你需要求出可能的听课方案中乐趣度最大的是多少以及具体的安排。

第一行两个整数 $n,m$。 接下来四行，每行一个整数序列，分别表示题目中的 $a,x,b,y$，这四个序列长度分别为 $n,n,m,m$。

第一行一个整数表示最大乐趣度。 第二行两个整数 $l_1,r_1$，如果你不打算在 THU 听课，输出 `0 0`。 第三行两个整数 $l_2,r_2$，如果你不打算在 PKU 听课，输出 `0 0`。

#### 【样例解释】 对于样例组 #1： 最优解如样例所示，课程质量之和为 $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$。 对于样例组 #2： 由于 PKU 的 $1$ 号、$2$ 号课程相比 THU 的相同课程的质量要高得多，因此最优解是不去 THU 听课，转而在 PKU 读 $1\sim 3$ 号课程。 #### 【数据范围】 注：本题只放部分数据，完整数据请左转 [LOJ P2773](https://loj.ac/p/2773) 评测。 对于所有数据满足：$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)$。 | 子任务编号 | 分值 | $1 \le n,m \le $ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $50$ | | $2$ | $10$ | $100$ | | $3$ | $10$ | $300$ | | $4$ | $10$ | $500$ | | $5$ | $10$ | $2000$ | | $6$ | $5$ | $5000$ | | $7$ | $5$ | $10^4$ | | $8$ | $10$ | $3 \times 10^4$ | | $9$ | $10$ | $10^5$ | | $10$ | $10$ | $2.5 \times 10^5$ | | $11$ | $10$ | $5 \times 10^5$ |