Deposit

Over many years of work, Vasily Ivanovich earned k rubles. He has now retired and wants to put this money on deposit for the next m years. His hometown has n banks. If Vasily Ivanovich keeps money in bank i during year j, the amount in that account increases by pi,j percent at the end of the year.

At the start of each year, Vasily Ivanovich may redistribute the money held in the bank accounts if he wants to. Redistribution happens in four stages. First he chooses the set of banks taking part in the redistribution. Then Vasily Ivanovich withdraws all the money held in those banks. After that he pays a fee to each of the chosen banks. Finally he deposits into each of the chosen banks as much money as he wants, and in total he deposits into the accounts all the money he withdrew minus the fees paid. The chosen set of banks may include banks where Vasily Ivanovich had no money or banks where he does not plan to put money. Bank i has a fee of ai rubles. If Vasily Ivanovich does not have enough money to pay the fees, he gives all the withdrawn money to the banks that took part in the redistribution.

At the start of the first year, Vasily Ivanovich may place any number of rubles on deposit in any banks free of charge, and in total he places all his money on deposit.

Find the maximum total number of rubles in all of Vasily Ivanovich's accounts at the end of year m.

In the example, Vasily Ivanovich first puts his money in the second bank. After the first year he has 115 rubles, and he chooses both banks for redistribution. After paying a fee of 2 rubles, he puts all the money in the first bank. At the end of the year he has 113×1.15=129.95 rubles in his bank account.

The first line contains the natural number t, the number of tests. (1 ≤ t ≤ 50)

The description of each test begins with a line containing three integers n, m, and k: the number of banks, the number of years, and the rubles earned. (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 109) The next line contains n integers, where the i-th number is ai, the fee of bank i. (1 ≤ ai ≤ 109) Each of the next n lines contains m integers. In the i-th line, the j-th number is pi,j, the percentage of additional money Vasily Ivanovich receives in year j on an account in bank i. (0 ≤ pi,j ≤ 100)

The total number of banks across all tests does not exceed 50000.

For each test, output on a separate line the maximum total amount of money in all of Vasily Ivanovich's accounts at the end of year m. Your answer is accepted if its relative error does not exceed 10−6.