22118번 - Депозит 스페셜 저지다국어

문제

За много лет трудового стажа Василий Иванович заработал k рублей. Теперь Василий Иванович вышел на пенсию и хочет положить эти деньги на депозит на ближайшие m лет. В его родном городе работает n банков. Если у Василия Ивановича в банке с номером i на протяжении j-го года на счету лежат деньги, то в конце года их количество на этом счету увеличится на p_i,_j процентов.

В начале каждого года Василий Иванович может, если хочет, перераспределить деньги лежащие на счетах в банках. Процесс перераспределения денег происходит в четыре этапа. Сначала он выбирает множество банков участвующих в перераспределении. Затем Василий Иванович снимает все деньги, лежащие в этих банках. После этого он платит комиссию каждому из выбранных банков. В конце в каждый из выбранных банков он кладет на счет столько денег, сколько он хочет, причем суммарно на счета Василий Иванович кладет все деньги, которые он снял, за вычетом уплаченной комиссии. При этом в множестве выбранных банков могут в том числе быть банки, где у Василия Ивановича не было денег, или в которые он не планирует деньги класть. У банка с номером i комиссия равна a_i рублей. Если у Василия Ивановича недостаточно денег, чтобы заплатить комиссию, то он отдает все снятые деньги банкам, участвовавшим в перераспределении денег.

В начале первого года Василий Иванович может бесплатно положить любое число рублей на депозиты в любые банки, причем суммарно на депозиты он положит все свои деньги.

Найдите максимальное суммарное число рублей на всех счетах Василия Ивановича в конце m-го года.

В примере Василий Иванович сначала кладет деньги во второй банк. После первого года у него 115 рублей, он выбирает для перераспределения оба банка. Уплатив комиссию 2 рубля, он кладет все деньги в первый банк. В конце года у него 113×1.15=129.95 рублей на счету в банке.

입력

В первой строке содержится натуральное число t — количество тестов. (1 ≤ t ≤ 50)

Описание каждого теста начинается со строки содержащей три целых числа n, m и k — количество банков, лет, и заработанных рублей соответственно. (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 10⁹) В следующей строке содержится n целых чисел, где i-е число равно a_i — комиссии i-го банка (1 ≤ a_i ≤ 10⁹) В каждой из следующих n строк содержится по m целых чисел. В i-й строке j-е число равно p_i,j — процент дополнительных денег, получаемых Василием Ивановичем в j-м году на счет в i-м банке (0 ≤ p_i,j ≤ 100).

Суммарное количество банков во всех тестах не превышает 50000.

출력

Для каждого теста в отдельной строке выведите максимальное суммарное количество денег на всех счетах Василия Ивановича в конце m-го года. Ваш ответ будет засчитан, если его относительная погрешность не превышает 10⁻⁶.

제한

힌트