【贪心6】小塔贴标签
问题分析
小塔需要给物品贴标签，每个物品只能贴上适合的标签或不贴标签。每种标签最多只能使用一次，因此需要在合理分配标签的情况下，最大化所有物品的美观值之和。
对于每个物品来说，有两个可能的美观值：
- 如果贴上适合的标签
a_i，则其美观值为 b_i。
- 如果没有贴上标签，则其美观值为
c_i。
P14351.【贪心6】小塔贴标签
本题为2024年9月21日美团机考原题
美团机考的介绍点击这里
题目内容
小塔正在给自己的物品贴标签。她一共有m种不同的标签，每种标签只有一个。
对于第i个物品，如果贴上ai号标签，那么它的美观值为bi;如果没有贴上ai号标签，则其美观值为ci。
小美想知道在合理的分配下，所有物品的美观值之和最大为多少。
输入描述
第一行输入两个整数n和m(1≤n,m≤105)代表小美的物品个数和标签种类。
第二行输入n个整数a1,a2,.,an(1≤ai≤m)代表每个物品适合的标签种类.
第三行输入n个整数b1,b2,..,bn(−10≤bi≤106)代表每个物品贴上适合的标签后的美观值。
第四行输入n个整数c1,c2,..,cn(−106≤ci≤106)代表每个物品未贴上适合标签时的美观值。
输出描述
在一行上输出一个整数，代表所有物品美观值之和的最大值。
样例
输入
3 3
1 2 1
5 4 3
-1 2 -100
输出
6
说明
只要把第二个物品贴上2号标签，第三个物品贴上1号标签，此时美观值之和为−1+4+3=6
