Депозит
За много лет трудового стажа Василий Иванович заработал k рублей. Теперь Василий Иванович вышел на пенсию и хочет положить эти деньги на депозит на ближайшие m лет. В его родном городе работает n банков. Если у Василия Ивановича в банке с номером i на протяжении j-го года на счету лежат деньги, то в конце года их количество на этом счету увеличится на p_i,_j процентов.
В начале каждого года Василий Иванович может, если хочет, перераспределить деньги лежащие на счетах в банках. Процесс перераспределения денег происходит в четыре этапа. Сначала он выбирает множество банков участвующих в перераспределении. Затем Василий Иванович снимает все деньги, лежащие в этих банках. После этого он платит комиссию каждому из выбранных банков. В конце в каждый из выбранных банков он кладет на счет столько денег, сколько он хочет, причем суммарно на счета Василий Иванович кладет все деньги, которые он снял. При этом в множестве выбранных банков могут в том числе быть банки, где у Василия Ивановича не было денег, или в которые он не планирует деньги класть. У банка с номером i комиссия равна a_i рублей. Если у Василия Ивановича недостаточно денег, чтобы заплатить комиссию, то он отдает все снятые деньги банкам, участвовавшим в перераспределении денег.
В начале первого года Василий Иванович может бесплатно положить любое число рублей на депозиты в любые банки, причем суммарно на депозиты он положит все свои деньги.
Найдите максимальное суммарное число рублей на всех счетах Василия Ивановича в конце m-го года.
Входные данные
В первой строке содержится натуральное число t — количество тестов (1 ≤ t ≤ 50).
Описание каждого теста начинается со строки содержащей три целых числа n, m и k — количество банков, лет, и заработанных рублей соответственно (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 10^9). В следующей строке содержится n целых чисел, где i-е число равно a_i — комиссии i-го банка (1 ≤ a_i ≤ 10^9). В каждой из следующих n строк содержится по m целых чисел. В i-й строке j-е число равно p_{i,j} — процент дополнительных денег, получаемых Василием Ивановичем в j-м году на счет в i-м банке (0 ≤ p_{i,j} ≤ 100).
Суммарное количество банков во всех тестах не превышает 50000.
Выходные данные
Для каждого теста в отдельной строке выведите максимальное суммарное количество денег на всех счетах Василия Ивановича в конце m-го года. Ваш ответ будет засчитан, если его относительная погрешность не превышает 10^{−6}.