선불금

큰 집을 사려면 많은 돈이 들기 때문에 보통 대출이 필요하다. 대출 기관은 다양한 상환 상품을 제공하는데, 예를 들어 일정 기간 동안 현재 이자율로 고정할 수 있다. 이 약정 기간 동안에는 기관을 바꾸거나 조건을 변경할 수 없다. 기간이 끝나면 위약금을 내고 다른 조건으로 바꾸거나 새로운 기간을 시작할 수 있다. 문제는 이자율이 매달 달라진다는 점이다.

이 문제에서는 당신에게 수정 구슬이 있다는 다소 황당한 가정을 한다. 즉, 모든 상품의 앞으로 매달 이자율을 미리 알고 있다. 이 정보를 이용하여, 대출 기간 전체에 걸쳐 지불하는 총액이 최소가 되도록 상환 계획을 세워라.

매달 빚은 다음과 같이 변한다.

1. 먼저 조건 변경에 따른 위약금이 빚에 더해진다. 맨 첫 달에는 위약금 없이 아무 상품이나 고를 수 있다.
2. 그다음, (방금 더한 위약금을 포함한) 현재 빚에 대한 이자가 더해진다.

두 항목을 모두 더한 뒤, 빚을 소수점 둘째 자리까지 0 방향으로 버림한다. 그런 다음 고정 금액을 상환하여 그만큼 빚을 줄인다. 만약 빚이 고정 금액보다 적다면 남은 빚만큼만 갚고 대출이 완전히 청산된다. 약정 기간이 끝나기 전에 대출을 다 갚더라도 위약금은 물지 않는다.

첫째 줄에 테스트 케이스의 수 정수 $N \le 50$이 주어진다.

각 테스트 케이스는 정수 $m$과 소수점 이하 최대 두 자리인 두 실수 $x$, $y$가 있는 줄로 시작한다. 여기서 $1 \le m \le 20$은 상품의 수, $1 \le x \le 1000000$은 대출 금액, $1 \le y \le 10000$은 매달 갚는 고정 금액이다.

다음 $m$개의 줄에는 각각 정수 $l$ ($1 \le l \le 60$)이 주어지며, 해당 상품의 약정 기간(개월)이다.

그다음 $m$개의 줄에는 각각 소수점 이하 최대 두 자리인 $m$개의 실수가 주어진다. 값 $C(a, b) \ge 0$은 상품 $a$에서 상품 $b$로 바꿀 때의 비용이며, $C(a, b) = C(b, a)$이고 $C(a, a) = 0$이다.

이어서 정수 $t$가 있는 줄이 주어진다. $t$는 이자율 정보가 주어지는 개월 수이며, 최적해를 구하기에 충분히 크다고 가정해도 된다.

마지막으로 $t$개의 줄에는 각각 $m$개의 실수(소수점 이하 최대 두 자리)가 주어지며, 해당 달의 각 상품 월 이자율을 퍼센트 단위로 나타낸다.

대출은 항상 100년 이내에 완전히 갚을 수 있으며, 모든 입력 줄의 길이는 255자를 넘지 않는다고 가정해도 된다.

각 테스트 케이스마다 Test case u 한 줄을 출력하고, 이어서 Total: s 한 줄을 출력한다. 여기서 $s$는 대출 기간 전체에 걸쳐 지불하는 총액의 최솟값이며, 소수점 이하 정확히 두 자리로 출력한다. 콜론(:) 뒤에는 공백을 정확히 하나만 둔다. $u$는 1부터 시작한다.