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