Minimizing Annual Coal Transportation and Operation Costs

In a certain region, there are \(m\) coal mines, where the \(i\)th mine produces \(a_i\) tons of coal per year. An existing thermal power plant requires exactly \(b\) tons of coal per year, and its annual fixed operating cost is \(h\) (excluding the coal transportation cost). The cost to transport one ton of raw coal from the \(i\)th mine to this plant is \(C_{i,0}\) yuan.

A new power plant is planned to be built. All raw coal produced by the \(m\) mines is supplied to the two power plants. There are \(n\) candidate sites for the new plant. If the new plant is built at candidate site \(j\), its annual fixed operating cost is \(h_j\), and the transportation cost per ton of coal from mine \(i\) to this site is \(C_{i,j}\) yuan.

The task is to choose one candidate site for the new plant and to allocate the raw coal from the \(m\) mines between the existing and the new plant so that the total annual cost (the sum of the operating costs and the coal transportation costs) is minimized.

For a chosen candidate \(j\), let \(x_i\) be the amount of coal transported from mine \(i\) to the existing power plant, and \(a_i - x_i\) the amount sent to the new plant. The following conditions must be met:

• \(0 \le x_i \le a_i\) for all \(i\).
• \(\sum_{i=1}^m x_i = b\) (since the existing plant requires exactly \(b\) tons).

The transportation cost for mine \(i\) will be \(x_i \cdot C_{i,0} + (a_i - x_i) \cdot C_{i,j}\). Thus, the total cost for candidate \(j\) is:

\[ \text{TotalCost}_j = h + h_j + \sum_{i=1}^{m} \left( a_i \cdot C_{i,j} + x_i (C_{i,0} - C_{i,j}) \right). \]

Since \(a_i \cdot C_{i,j}\) is fixed regardless of the allocation, the problem reduces to choosing \(x_i\) for each mine (subject to \(\sum_{i=1}^m x_i = b\)) that minimizes \(\sum_{i=1}^{m} x_i (C_{i,0} - C_{i,j})\). This can be solved greedily by sorting the mines by \(d_i = C_{i,0} - C_{i,j}\) in ascending order and allocating as much as possible in that order until the sum \(b\) is reached.

Your program should compute the minimal total annual cost among all candidate sites.

inputFormat

The input is given in the following format:

 m n b h
 a1 a2 ... am
 C1,0 C2,0 ... Cm,0
 h1 h2 ... hn
 C1,1 C2,1 ... Cm,1
 C1,2 C2,2 ... Cm,2
 ...
 C1,n C2,n ... Cm,n

Here,

• \(m\): The number of coal mines.
• \(n\): The number of candidate sites for the new power plant.
• \(b\): The required amount of coal (in tons) for the existing power plant.
• \(h\): The fixed annual operating cost for the existing power plant.
• \(a_i\): The production (in tons) of the \(i\)th mine.
• \(C_{i,0}\): The transportation cost (per ton) from mine \(i\) to the existing power plant.
• \(h_j\): The fixed annual operating cost if the new power plant is built at candidate site \(j\).
• \(C_{i,j}\): The transportation cost (per ton) from mine \(i\) to candidate site \(j\) (for the new power plant).

You may assume that \(\sum_{i=1}^{m} a_i \ge b\) so that it is always possible to meet the existing plant's requirement.

outputFormat

Output a single integer representing the minimal total annual cost, which is the sum of the fixed operating costs and the minimal transportation cost achievable by an optimal allocation of coal from the mines between the two power plants.

sample

3 2 5 100
3 4 5
1 2 3
50 60
2 3 5
3 1 6

183