#P3745. [六省联考 2017] 期末考试

    ID: 20 远端评测题 1000ms 512MiB 尝试: 4 已通过: 3 难度: 10 上传者: 标签>数学贪心2017各省省选枚举,暴力前缀和

[六省联考 2017] 期末考试

题目描述

nn 位同学,每位同学都参加了全部的 mm 门课程的期末考试,都在焦急的等待成绩的公布。

ii 位同学希望在第 tit_i 天或之前得知所有课程的成绩。如果在第 tit_i 天,有至少一门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产生 CC 不愉快度。

对于第 ii 门课程,按照原本的计划,会在第 bib_i 天公布成绩。

有如下两种操作可以调整公布成绩的时间:

  1. 将负责课程 XX 的部分老师调整到课程 YY,调整之后公布课程 XX 成绩的时间推迟一天,公布课程 YY 成绩的时间提前一天;每次操作产生 AA 不愉快度。
  2. 增加一部分老师负责学科 ZZ,这将导致学科 ZZ 的出成绩时间提前一天;每次操作产生 BB 不愉快度。

上面两种操作中的参数 X,Y,ZX, Y, Z 均可任意指定,每种操作均可以执行多次,每次执行时都可以重新指定参数。

现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快度之和即可。

输入格式

第一行三个非负整数 A,B,CA, B, C,描述三种不愉快度,详见【题目描述】;
第二行两个正整数 n,mn, m,分别表示学生的数量和课程的数量;
第三行 nn 个正整数 tit_i,表示每个学生希望的公布成绩的时间;
第四行 mm 个正整数 bib_i,表示按照原本的计划,每门课程公布成绩的时间。

输出格式

输出一行一个整数,表示最小的不愉快度之和。

100 100 2
4 5
5 1 2 3
1 1 2 3 3
6
3 5 4
5 6
1 1 4 7 8
2 3 3 1 8 2
33

提示

样例解释 1

由于调整操作产生的不愉快度太大,所以在本例中最好的方案是不进行调整;全部的 55 门课程中,最慢的在第 33 天出成绩;
同学 11 希望在第 55 天或之前出成绩,所以不会产生不愉快度;
同学 22 希望在第 11 天或之前出成绩,产生的不愉快度为 (31)×2=4(3 - 1) \times 2 = 4
同学 33 希望在第 22 天或之前出成绩,产生的不愉快度为 (32)×2=2(3 - 2) \times 2 = 2
同学 44 希望在第 33 天或之前出成绩,所以不会产生不愉快度;
不愉快度之和为 4+2=64 + 2 = 6

数据范围

Case # n,m,ti,bin, m, t_i, b_i A,B,CA, B, C
1, 2 1n,m,ti,bi20001 \leq n, m, t_i, b_i \leq 2000 A=109;B=109;0C102A = 10^9; B = 10^9; 0 \leq C \leq 10^2
3, 4 0A;C102;B=1090 \leq A; C \leq 10^2; B = 10^9
5, 6, 7, 8 0BA102;0C1020 \leq B \leq A \leq 10^2; 0 \leq C \leq 10^2
9 - 12 0A,B,C1020 \leq A, B, C \leq 10^2
13, 14 1n,m,ti,bi1051 \leq n, m, t_i, b_i \leq 10^5 0A,B105;C=10160 \leq A, B \leq 10^5; C = 10^{16}
15 - 20 0A,B,C1050 \leq A, B, C \leq 10^5