Minimized Disutility for Exam Score Announcements

There are n students and m courses. For each course i, the exam score is scheduled to be announced on day \(b_i\). Each student j expects to know all his/her scores by day t_j. If on day t_j at least one course’s score isn't announced, the student will wait until the last score is announced; every day of waiting adds a disutility cost of C for that student.

Two types of operations can adjust the publication dates:

1. Transfer a part of the teaching staff from course X to course Y. As a result, the announcement day for course X is postponed by one day, while that for course Y is advanced by one day. Each such operation incurs a disutility cost of A.
2. Increase the number of teachers for course Z, which will cause the announcement day for course Z to be advanced by one day. Each such operation incurs a disutility cost of B.

Operations can be performed arbitrarily many times with any valid choices of X, Y and Z at each step. The final publication day for each course is determined after all operations, and the overall waiting time for a student is determined by the latest announcement day among the courses.

The goal is to perform a series of operations to minimize the total disutility, which is the sum of the waiting disutility for all students and the disutility costs of all operations. Formally, if after operations the announcement days become \(p_1, p_2, \dots, p_m\) (with \(D = \max_{i=1}^{m} p_i\)), then:

Total disutility = [Operation cost] + \(\displaystyle \sum_{j=1}^{n} C \cdot \max(0, D - t_j)\).

The adjustment operations affect only the publication dates. For any course that originally had date \(b_i\) and must be reduced to at most \(D\) (if \(b_i > D\)), the total reduction required is \(b_i - D\). You can reduce a course’s date by either of the following methods:

• If A \ge B, it is always optimal to use operation 2 (which decreases the date by one at cost \(B\)) for each day of reduction. Hence, the cost for course i is \((b_i - D) \times B\) (if \(b_i > D\); zero otherwise).
• If A < B, you can use operation 1 to transfer a reduction from a course with \(b_i > D\) at cost \(A\) per day. However, each use of operation 1 also forces increasing one course’s date by one. Such an increase is only allowed if the course’s new date does not exceed \(D\). For every course with initial date \(b_i \le D\), it can absorb at most \(D - b_i\) increases. Let \(X\) be the total increase capacity of courses with \(b_i \le D\) and let \(R\) be the total days that courses with \(b_i > D\) need to be decreased, i.e., \(R = \sum_{b_i > D} (b_i - D)\). Then, up to \(\min(R, X)\) days of reduction can be performed using operation 1 at cost A per day; the remaining \(R - \min(R, X)\) days will be adjusted by operation 2 at cost B per day.

Your task is to choose a final announcement day \(D\) (an integer) and a schedule of operations so that the overall total disutility is minimized. Output that minimum total disutility cost.

Note: All mathematical formulas are given in LaTeX format.

inputFormat

The first line contains five integers: n, m, A, B, and C, where

• n is the number of students,
• m is the number of courses,
• A is the disutility cost for operation 1,
• B is the disutility cost for operation 2, and
• C is the daily waiting disutility cost per student.

The second line contains n integers \(t_1, t_2, \dots, t_n\) where \(t_j\) is the day student j expects all scores.

The third line contains m integers \(b_1, b_2, \dots, b_m\) where \(b_i\) is the originally scheduled announcement day for course i.

outputFormat

Output a single integer — the minimum total disutility cost achievable by an optimal sequence of operations.

sample

2 2 3 5 2
2 5
3 8

17