#CW25. 茶歇搭配(flavor)

茶歇搭配(flavor)

题目描述

小 W 正在为一次活动准备茶歇。桌上有 nn 份点心和 mm 杯饮品,其中 n≥mn \ge m。每份点心有一种口味和一个基础满意度,每杯饮品也有一种口味和一个搭配加成。

第 ii 份点心的口味为 xix_i,基础满意度为 pip_i;第 jj 杯饮品的口味为 yjy_j,搭配加成为 qjq_j。

小 W 需要选出恰好 mm 份点心,并将它们与 mm 杯饮品一一配对。若点心 ii 与饮品 jj 的口味相同,这一组的满意度为 pi+qjp_i+q_j;否则,这一组的满意度为 pip_i。

请计算所有组的满意度之和最大是多少。

输入格式

第一行输入两个整数 n,mn,m。

第二行输入 nn 个整数 x1,x2,…,xnx_1,x_2,\dots,x_n,表示每份点心的口味。

第三行输入 nn 个整数 p1,p2,…,pnp_1,p_2,\dots,p_n,表示每份点心的基础满意度。

第四行输入 mm 个整数 y1,y2,…,ymy_1,y_2,\dots,y_m,表示每杯饮品的口味。

第五行输入 mm 个整数 q1,q2,…,qmq_1,q_2,\dots,q_m,表示每杯饮品的搭配加成。

输出格式

输出一个整数,表示满意度之和的最大值。

样例 1 输入

4 2
1 2 1 3
5 4 1 8
1 2
10 3

样例 1 输出

23

样例 1 解释

可以选择基础满意度为 55 的 11 号口味点心,并将它与加成为 1010 的同口味饮品配对;再选择基础满意度为 88 的 33 号点心。总满意度为 15+8=2315+8=23。

样例 2 输入

6 4
1 1 2 2 3 4
8 3 7 6 9 1
1 2 2 5
4 10 2 100

样例 2 输出

46

数据范围

对于所有测试数据,保证:

  • 1≤m≤n≤2×1051 \le m \le n \le 2\times 10^5;
  • 1≤xi,yj≤n1 \le x_i,y_j \le n;
  • 0≤pi,qj≤1090 \le p_i,q_j \le 10^9。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤20n \le 20
B 15 3∼53\sim 5 n≤1000n \le 1000
C 20 6∼96\sim 9 所有 pi=0p_i=0
D 25 10∼1410\sim 14 每种口味的点心不超过 33 份
E 30 15∼2015\sim 20 无额外限制