Description

There are $m$ coal mines in a region, where the $i$-th mine produces $a_i$ tons per year. There is an existing thermal power plant that requires exactly $b$ tons of coal per year. Its fixed annual operating cost (excluding coal transportation) is $h$ yuan. The transportation cost per ton of raw coal from the $i$-th mine to the existing plant is $C_{i,0}$ yuan.

A new power plant is planned to be built. All raw coal mined from the $m$ mines will be entirely supplied to these two power plants. There are $n$ candidate sites for the new plant. If the new plant is built at the $j$-th candidate site, its fixed annual operating cost is $h_j$ yuan, and the transportation cost per ton of raw coal from the $i$-th mine to the $j$-th candidate site is $C_{i,j}$ yuan.

Question: Which site should be selected for the new plant, and how should the raw coal from the $m$ mines be allocated to the two plants, so that the total annual cost (the sum of the plants’ operating costs and the coal transportation costs) is minimized?

Input Format

The first line contains four integers $m, b, h, n$.

The next line contains $m$ integers $a_1, a_2, \ldots, a_m$, representing the annual output of each coal mine.

The next line contains $n$ integers $h_1, h_2, \ldots, h_n$, representing the fixed cost if the new plant is built at each candidate site.

The next $n+1$ lines each contain $m$ positive integers. The $i$-th line describes the values of $C_{1,i-1} , C_{2,i-1} , \ldots , C_{m , i-1}$.

Output Format

The first line contains one integer, the index of the selected site for the new power plant. If multiple sites satisfy the condition, output the smallest index.

The second line contains one integer, the minimal total annual cost.

4 2 7 9 
3 1 10 3 
6 3 7 1 10 2 7 4 9 
1 2 4 3 
6 6 8 2 
4 10 8 4 
10 2 9 2 
7 6 6 2 
9 3 7 1 
2 1 6 9 
3 1 10 9 
4 2 1 8 
2 1 3 4 

8 
49 

Hint

For $100 \%$ of the testdata (Constraints): $1 \leq m \leq 5 \times 10^4$, $1 \leq b \leq 10^4$, $1 \leq n \leq 50$, $0 \leq h , h_i \leq 100$, $0 \leq a_i \leq 500$, $\sum\limits_{i=1}^m a_i \geq b$, $0 \leq C_{i,j} \leq 50$.

Translated by ChatGPT 5