题目描述
Problem Description
There are $n$ students, each of whom has taken the final exams for all $m$ courses and is anxiously waiting for the results.
The $i$-th student hopes to know all the results by day $t_i$ or earlier. If by day $t_i$, at least one course result has not been announced, he will wait until the last course result is announced, with each day of waiting incurring an unpleasantness level of $C$.
For the $i$-th course, according to the original plan, the results will be announced on day $b_i$.
There are two types of operations to adjust the announcement times:
1. Transfer some teachers from course $X$ to course $Y$, which will delay the announcement of course $X$ by one day and advance the announcement of course $Y$ by one day; each operation incurs an unpleasantness level of $A$.
2. Increase the number of teachers responsible for course $Z$, which will advance the announcement of course $Z$ by one day; each operation incurs an unpleasantness level of $B$.
The parameters $X, Y, Z$ in the above operations can be arbitrarily specified, and each operation can be performed multiple times, with each execution allowing the parameters to be re-specified.
You are now asked to perform reasonable operations to minimize the total unpleasantness level, and output the minimum total unpleasantness level.
Input Format
The first line contains three non-negative integers $A, B, C$, describing the three types of unpleasantness levels, as detailed in the problem description.
The second line contains two positive integers $n, m$, representing the number of students and the number of courses, respectively.
The third line contains $n$ positive integers $t_i$, indicating the day by which each student hopes to know the results.
The fourth line contains $m$ positive integers $b_i$, indicating the day on which each course's results are planned to be announced.
Output Format
Output a single integer, representing the minimum total unpleasantness level.
Sample Input and Output
Input Sample #1
100 100 2
4 5
5 1 2 3
1 1 2 3 3
Output Sample #1
6
Input Sample #2
3 5 4
5 6
1 1 4 7 8
2 3 3 1 8 2
Output Sample #2
33
Notes/Hints
Sample Explanation 1
Since the unpleasantness level from adjustment operations is too high, the best solution in this example is not to make any adjustments; among all $5$ courses, the slowest one will announce results on day $3$;
Student $1$ hopes to know the results by day $5$ or earlier, so no unpleasantness level is incurred;
Student $2$ hopes to know the results by day $1$ or earlier, incurring an unpleasantness level of $(3 - 1) \times 2 = 4$;
Student $3$ hopes to know the results by day $2$ or earlier, incurring an unpleasantness level of $(3 - 2) \times 2 = 2$;
Student $4$ hopes to know the results by day $3$ or earlier, so no unpleasantness level is incurred;
The total unpleasantness level is $4 + 2 = 6$.
Data Range
| Case # | $n, m, t_i, b_i$ | $A, B, C$ |
|---|---|---|
| 1, 2 | $1 \leq n, m, t_i, b_i \leq 2000$ | $A = 10^9; B = 10^9; 0 \leq C \leq 10^2$ |
| 3, 4 | $1 \leq n, m, t_i, b_i \leq 2000$ | $0 \leq A; C \leq 10^2; B = 10^9$ |
| 5, 6, 7, 8 | $1 \leq n, m, t_i, b_i \leq 2000$ | $0 \leq B \leq A \leq 10^2; 0 \leq C \leq 10^2$ |
| 9 - 12 | $1 \leq n, m, t_i, b_i \leq 2000$ | $0 \leq A, B, C \leq 10^2$ |
| 13, 14 | $1 \leq n, m, t_i, b_i \leq 10^5$ | $0 \leq A, B \leq 10^5; C = 10^{16}$ |
| 15 - 20 | $1 \leq n, m, t_i, b_i \leq 10^5$ | $0 \leq A, B, C \leq 10^5$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分