예금

바실리 이바노비치는 오랜 근무 기간 동안 k루블을 모았다. 이제 그는 은퇴했고, 이 돈을 앞으로 m년 동안 예금에 넣으려 한다. 그의 고향에는 n개의 은행이 있다. 바실리 이바노비치가 i번 은행에 j번째 해 동안 돈을 예치해 두면, 그 해 말에 이 계좌의 금액이 pi,j퍼센트 증가한다.

매년 초에 바실리 이바노비치는 원하면 은행 계좌에 있는 돈을 재분배할 수 있다. 재분배 과정은 네 단계로 이루어진다. 먼저 재분배에 참여할 은행 집합을 고른다. 그다음 바실리 이바노비치는 그 은행들에 있는 돈을 모두 인출한다. 그 후 선택한 각 은행에 수수료를 지불한다. 마지막으로 선택한 각 은행에 원하는 만큼 돈을 예치하는데, 인출한 돈에서 수수료를 뺀 전액을 선택한 은행 계좌에 합계로 예치한다. 이때 선택한 은행 집합에는 바실리 이바노비치가 돈을 넣어 두지 않았던 은행이나 돈을 넣을 계획이 없는 은행도 포함될 수 있다. i번 은행의 수수료는 ai루블이다. 수수료를 지불할 돈이 부족하면, 그는 인출한 돈 전부를 재분배에 참여한 은행에 넘긴다.

첫해 초에 바실리 이바노비치는 원하는 은행에 아무 금액이나 무료로 예금할 수 있으며, 자신의 돈 전부를 예금에 넣는다.

m번째 해 말에 바실리 이바노비치의 모든 계좌에 있는 최대 총 금액을 구하시오.

예시에서 바실리 이바노비치는 먼저 두 번째 은행에 돈을 넣는다. 첫해가 지나면 115루블이 있고, 두 은행 모두를 재분배 대상으로 선택한다. 수수료 2루블을 내고 모든 돈을 첫 번째 은행에 넣는다. 그해 말에 은행 계좌에는 113×1.15=129.95루블이 있다.

첫째 줄에 테스트의 수 t가 주어진다. (1 ≤ t ≤ 50)

각 테스트의 설명은 n, m, k 세 정수를 포함하는 줄로 시작한다. 각각 은행의 수, 연수, 모은 루블이다. (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 109) 다음 줄에 n개의 정수가 주어지며, i번째 수는 i번 은행의 수수료 ai이다. (1 ≤ ai ≤ 109) 다음 n개의 줄 각각에는 m개의 정수가 있다. i번째 줄의 j번째 수는 j번째 해에 i번 은행 계좌에서 바실리 이바노비치가 받는 추가 금액의 비율 pi,j이다. (0 ≤ pi,j ≤ 100)

모든 테스트의 은행 수 합계는 50000을 넘지 않는다.

각 테스트마다 m번째 해 말에 바실리 이바노비치의 모든 계좌에 있는 최대 총 금액을 한 줄에 출력한다. 상대 오차가 10−6을 넘지 않으면 정답으로 인정된다.