Optimal Car Docking Time Calculation

You are given n docking stations and m cars. Each docking station i has a capacity c_i indicating the maximum number of cars it can hold. In addition, each car has an associated docking time. You are also given a list of m docking times. Your task is to assign cars to the available docking stations in such an order that the total docking time is minimized. This is achieved by docking the cars with the highest docking times at the most capacious stations.

In more formal terms, let \( C = [c_1, c_2, \dots, c_n] \) be the capacities and \( D = [d_1, d_2, \dots, d_m] \) the docking times. After sorting C and D in non-increasing order, the total docking time computed is: \[ T = \sum_{i=1}^{n} \sum_{j=1}^{c_i} d_{k(i, j)}, \] where \( k(i, j) \) is the index of the car assigned, if available. If there are not enough cars to fill all docking slots, the remaining slots contribute 0 to the total docking time.

If either the number of docking stations is 0 or no cars are available, the total docking time is 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 c1 c2 ... cn
 d1 d2 ... dm

Here, n is the number of docking stations, m is the number of cars, the second line contains n space-separated integers representing the capacities of each docking station, and the third line contains m space-separated integers representing the docking times of the cars.

outputFormat

The output should be written to standard output (stdout) and is a single integer representing the minimum total docking time after optimally assigning the cars.

3 7
2 3 4
1 2 3 4 5 6 7

28