P15791 「1&0OI R1」空洞

*而预感，正是未必成真，也未必绝不成真的侥幸。* >$\text{\textcolor{66CCFF}{被掏空的心和满怀空白谱纸一样凄清}}$ > >$\text{\textcolor{66CCFF}{误以为油墨味便是}\textcolor{EE0000}{你}\textcolor{66CCFF}{留下的气息}}$ 误解的妄想，既从不真实的背叛中生发出恨意，又在萦杂的情丝中维系着明天。 而误解的题目，既是对赛时的绝望挥霍，也是对新的创造可能的发见。 本题，即是脱胎于 $\text{\textcolor{0000FF}{L}}$ 在某场比赛读题时所犯的『错误』。

给定一个长为 $n$ 的序列 $a$，满足其中任意项是 $[1,m]$ 内的整数。有一个初始为空的序列 $b$，你可以通过进行任意次如下操作将 $b$ 变为 $a$： - 生成一个非空序列 $c$，其需要满足每一项均为 $[1,m]$ 内的整数，并把其追加在序列 $b$ 的后面。 有一个长度为 $m$ 的序列 $t$，与你的操作的得分有关。定义当你向序列 $b$ 后面追加序列 $c$ 时，你的得分为： $$\sum_{1\le x \le m,x \in b \land x \in c} t_x$$ 即所有既在序列 $b$ 中也在序列 $c$ 中的数 $x$ 的 $t_x$ 之和。**注意按此定义，$c$ 中相同的多个数只会贡献一次得分。** 你的总得分为把 $b$ 从空序列变为 $a$ 的过程中所有操作的得分之和。请输出你能获得的最大的总得分。

第一行输入两个正整数，分别代表 $n$ 和 $m$。 第二行输入 $n$ 个正整数，代表 $a_1,\ldots,a_n$。 第二行输入 $m$ 个整数，代表 $t_1,\ldots,t_m$。

输出一个整数，表示可能获得的总得分的最大值。 **保证答案在 `long long` 范围内。**

**【样例解释】** 对于样例 \#1，一种得到最大得分的方案为依次在序列末尾加入 $\{1,2\},\{1\},\{2\},\{3\}$，每次操作的得分分别为 $0,2,1,0$，总和为 $3$。 对于样例 \#2，一种得到最大得分的方案为依次在序列末尾加入 $\{1,1,2,3,5\},\{5,4,3\},\{6,6\}$，每次操作的得分分别为 $0,4,0$，总和为 $4$。 对于样例 \#3，一种得到最大得分的方案为依次在序列末尾加入 $\{1,2 \},\{3,4,3,2\},\{7,7,8,6,1\}$，每次操作的得分分别为 $0,12,20$，总和为 $32$。 对于样例 \#4，一种得到最大得分的方案为依次在序列末尾加入 $\{5\},\{2,6,3,4,1,5,6\}$，每次操作的得分分别为 $0,16$，总和为 $16$。 **可以证明以上四个样例不能获得更大的得分。** **【数据范围】** 对于所有测试点，有： - $1 \le n,m\le 5 \times 10^5$； - $1 \le a_i \le m$； - $-10^9 \le t_i \le 10^9$。 **请注意 $t_i$ 可能为负数。** 每个测试点的具体数据范围和特殊性质见下表。 ::cute-table{tuack} |测试点编号| $n \le $ | 特殊性质 | |:---:|:-:|:-:| | $1\sim2$ | $100$ | 无 | | $3\sim4$ | $5000$ | ^ | | $5\sim6$ | $5 \times 10^5$ | $t_i \ge 0$ | | $7\sim10$ | ^ | 无 |