P3745 [Six-Province Joint Exam 2017] Final Exam

There are $n$ students. Each student took the final exams of all $m$ courses and is anxiously waiting for the results to be announced. Student $i$ hopes to know the results of all courses on or before day $t_i$. If on day $t_i$ at least one course has not been announced, the student will wait until the last course is announced; each day of waiting incurs $C$ unhappiness. For course $i$, according to the original plan, its result will be announced on day $b_i$. You can adjust announcement days using the following two operations: 1. Move some teachers from course $X$ to course $Y$. After the adjustment, the announcement day of course $X$ is delayed by one day, and that of course $Y$ is moved one day earlier. Each such operation incurs $A$ unhappiness. 2. Add some teachers to course $Z$, which moves the announcement day of course $Z$ one day earlier. Each such operation incurs $B$ unhappiness. In both operations, the parameters $X$, $Y$, and $Z$ can be chosen arbitrarily. Each operation can be performed multiple times, and the parameters can be re-chosen each time. Please minimize the total unhappiness by applying operations reasonably, and output the minimum possible total unhappiness.

- The first line contains three non-negative integers $A, B, C$, which are the unhappiness costs, as described in the Description. - The second line contains two positive integers $n, m$, the numbers of students and courses, respectively. - The third line contains $n$ positive integers $t_i$, the desired announcement days for each student. - The fourth line contains $m$ positive integers $b_i$, the originally planned announcement days for each course.

Output a single integer on one line, the minimum total unhappiness.

### Sample Explanation 1 Because the unhappiness caused by adjustments is too large, the best plan here is to make no adjustments. Among all $5$ courses, the slowest is announced on day $3$. Student $1$ hopes for results by day $5$, so no unhappiness is incurred. Student $2$ hopes for results by day $1$, so the incurred unhappiness is $(3 - 1) \times 2 = 4$. Student $3$ hopes for results by day $2$, so the incurred unhappiness is $(3 - 2) \times 2 = 2$. Student $4$ hopes for results by day $3$, so no unhappiness is incurred. The total unhappiness is $4 + 2 = 6$. ### Constraints | 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$ | Translated by ChatGPT 5