Deposit#5760
Over the years, Victor Ivanescu has saved up euros. Now retired, he plans to invest this money for the next years. In his town, there are banks available. If Victor Ivanescu keeps his money in bank during year , the amount in his account will grow by p_{i,j} percent by the end of that year.
At the start of each year, Victor Ivanescu has the option to redistribute his funds among the banks. This redistribution involves four steps: first, he selects which banks to include in the redistribution. Next, he withdraws all his money from these banks. Then, he pays a commission to each selected bank. Finally, he can deposit any amount of money back into these banks, as long as the total deposited equals the total withdrawn. The selected banks can include those where he had no prior deposits or where he does not intend to deposit money. The commission for bank is a_i euros. If he doesn't have enough money to cover the commission, he must give all the withdrawn money to the banks involved in the redistribution.
At the beginning of the first year, Victor Ivanescu can freely distribute his entire savings among the banks, ensuring the total deposited equals his total savings.
Determine the maximum total amount of euros Victor Ivanescu can have in all his accounts at the end of the -th year.
The first line contains a natural number , representing the number of test cases (1 \leq t \leq 50).
Each test case starts with a line containing three integers , , and , which represent the number of banks, the number of years, and the amount of money Victor Ivanescu has saved, respectively (1 \leq n \leq 10000, 1 \leq m \leq 20, 1 \leq k \leq 10^9). The next line contains integers, where the -th integer is a_i, the commission for bank (1 \leq a_i \leq 10^9). Following this, there are lines, each containing integers. In the -th line, the -th integer is p_{i,j}, the percentage increase for the -th year in bank (0 \leq p_{i,j} \leq 100).
The total number of banks across all tests does not exceed .
For each test case, output the maximum total amount of money Victor Ivanescu can have in all his accounts at the end of the -th year, on a separate line. Your answer will be accepted if its relative error does not exceed 10^{-6}.
Example 1