Optimal Chef Hiring

Tom's Kitchen is a famous restaurant where every dish is prepared by at least \(K\) different chefs. Today, there are \(N\) dishes to prepare, and the \(i\)-th dish requires exactly \(A_i\) hours of total work. Tom can hire up to \(M\) chefs. The \(j\)-th chef, if hired, can work at most \(B_j\) hours. Note that regardless of the actual hours worked, if a chef is hired, he is paid for the full \(B_j\) hours. A chef may work on several dishes (allocating a positive integer number of hours on each dish he contributes to) but in each dish every chef’s contribution counts only once; that is, every dish must be worked on by at least \(K\) distinct chefs and the sum of their contributed hours must equal \(A_i\) exactly.

Tom wants to minimize the number of "wasted hours", which is defined as the total paid working hours (i.e. the sum of \(B_j\) for each hired chef) minus the total required working hours (i.e. \(\sum_{i=1}^{N}A_i\)). In other words, if the hired set of chefs is \(S\), then the wasted hours equal \(\left(\sum_{j\in S}B_j\right)-\left(\sum_{i=1}^{N}A_i\right)\). Help Tom choose a subset of chefs so that all dishes can be prepared under these conditions and the wasted hours are minimized. If it is impossible to prepare all dishes under these constraints, output -1.

Note:

• For each dish, besides totaling \(A_i\) hours, the work must be divided among at least \(K\) distinct chefs with each contributing a positive integer number of hours.
• If a chef is not hired then he does not contribute (and is not paid). Once a chef is hired, his full capacity \(B_j\) is paid regardless of how many hours he actually works.
• You may assume that a chef can work on any dish.

Hint: One way to think of the problem is as selecting a subset \(S\) of chefs (subject to \(|S| \ge K\)) such that:

1. It is possible to assign each dish \(K\) mandatory hours from \(K\) different chefs in \(S\) (each chef can only contribute at most one hour per dish for this purpose);
2. The total capacity of the hired chefs \(\left(\sum_{j\in S} B_j\right)\) is at least \(\sum_{i=1}^{N}A_i\) (so the extra hours can be allocated arbitrarily among chefs).

The wasted hours are \(\left(\sum_{j\in S} B_j\right)-\left(\sum_{i=1}^{N}A_i\right)\). Your task is to choose \(S\) so that the wasted hours are minimized.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) representing the number of dishes, the number of available chefs, and the minimum number of chefs required per dish, respectively.

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), where \(A_i\) is the total number of hours required to prepare the \(i\)-th dish.

The third line contains \(M\) integers \(B_1, B_2, \dots, B_M\), where \(B_j\) is the maximum number of hours chef \(j\) can work (and the number of hours he gets paid if hired).

outputFormat

Output a single integer which is the minimum wasted hours under an optimal hiring scheme. If it is impossible to prepare all dishes under the given constraints, output -1.

sample

2 3 2
3 3
2 4 4

0