思路

先假设所有物品都没有贴到“匹配标签”，此时总和为 $\displaystyle \text{base}=\sum_{i=1}^{n} c_i$。

若把某个物品 $i$ 贴上它匹配的 $a_i$ 号标签，总和会增加 $\displaystyle \Delta_i = b_i - c_i$。

由于每种标签只有 $1$ 张，对于同一标签种类 $t$，最多只能选择 一个满足 $a_i=t$ 的物品来获得这次“增量”。为了使总和最大，我们对每个标签种类 $t\in[1,m]$，只需挑选该类下的最大增量

题目内容

小美正在给自己的物品贴标签。她一共有$m$种不同的标签，每种标签只有一个。 对于第$i$个物品，如果贴上$a_i$号标签，那么它的美观值为$b_i$;如果没有贴上$a_i$号标签，则其美观值为$c_i$。 小美想知道在合理的分配下，所有物品的美观值之和最大为多少。

输入描述

第一行输入两个整数$n$和$m$($1≤n,m≤10^5$)代表小美的物品个数和标签种类。 第二行输入$n$个整数$a_1,a_2,.,a_n$($1≤a_i≤m$)代表每个物品适合的标签种类. 第三行输入$n$个整数$b_1, b_2,..,b_n$($-10^6≤b_i≤10^6$)代表每个物品贴上适合的标签后的美观值。 第四行输入$n$个整数$c1, c2,..,c_n$($-10^6≤c_i≤10^6$)代表每个物品未贴上适合标签时的美观值。

输出描述

在一行上输出一个整数，代表所有物品美观值之和的最大值。

样例1

输入

3 3
1 2 1
5 4 3
-1 2 -100

输出

6

说明

只要把第二个物品贴上$2$号标签，第三个物品贴上$1$号标签，此时美观值之和为$-1+4+3=6$