변환술

당신은 금, 백금, 은과 같은 금속은 흥미롭지 않다고 여기지만 납은 매우 귀하게 여기는 어느 나라에서 가장 뛰어난 연금술사이다. 세상에는 M개의 알려진 금속이 있으며, 당신의 주기율표에서 납은 1번 금속이다. 나라의 지도자는 국고에 있는 금속을 사용하여 가능한 한 많은 납을 만들라고 요청했다.

납을 포함한 각 금속에 대해, 재료가 되는 두 금속을 각각 한 그램씩 소모하여 해당 금속 한 그램을 만들 수 있는 공식을 정확히 하나 알고 있다. (질량 보존의 원리가 궁금하다면, 나머지 한 그램은 쓸모없는 폐기물로 손실된다.) 이 공식들은 그램의 일부 단위에는 적용되지 않는다. 하지만 매번 필요한 재료를 가지고 있기만 하면, 각 공식을 원하는 만큼 여러 번 사용할 수 있으며 전혀 사용하지 않아도 된다.

최적의 선택을 한다면, 최종적으로 얻을 수 있는 납의 총량의 최댓값은 얼마인가? 모든 작업을 마친 뒤 납 이외의 금속이 일부 남을 수도 있음에 유의하라.

제한

1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $R_{i1}$ < $R_{i2}$ ≤ M. 시간 제한: 테스트 세트당 5초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

2 ≤ M ≤ 8. 모든 i에 대해 0 ≤ $G_{i}$ ≤ 8.

테스트 세트 2 (비공개)

2 ≤ M ≤ 100. 모든 i에 대해 0 ≤ $G_{i}$ ≤ 100.

테스트 세트 3 (비공개)

2 ≤ M ≤ 100. 모든 i에 대해 0 ≤ $G_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세상에 알려진 금속의 수를 나타내는 정수 M이 있는 한 줄로 시작한다. 그다음에는 각각 두 정수 $R_{i1}$와 $R_{i2}$가 있는 M개의 줄이 더 주어진다. 이 줄들 중 i번째 줄은 $R_{i1}$번 금속 한 그램과 $R_{i2}$번 금속 한 그램을 소모하여 i번 금속 한 그램을 만들 수 있음을 나타낸다. 마지막으로 M개의 정수 $G_{1}$, $G_{2}$, ..., $G_{M}$가 있는 한 줄이 주어지며, $G_{i}$는 국고에 있는 i번 금속의 그램 수이다. 납은 1번 금속이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 최종적으로 얻을 수 있는 납의 양의 최댓값을 그램 단위로 나타낸다.

예제 케이스 #1에서 최적의 전략은 2번 금속과 3번 금속을 각각 2그램 사용하여 납을 2그램 더 만들고, 총 7그램의 납을 얻는 것이다.

예제 케이스 #2에서 최적의 전략은 먼저 3번 금속 2그램과 5번 금속 2그램을 사용하여 4번 금속 2그램을 만든 다음, 3번 금속 4그램과 4번 금속 4그램을 사용하여 납 4그램을 만드는 것이다. 두 공식이 동일한 두 재료를 가질 수도 있음에 유의하라(단지 서로 다른 연금술 기법을 사용한다). 또한 모든 금속이 반드시 다른 어떤 공식의 재료로 쓰이는 것은 아니다. 이 경우 2번 금속은 재료로 전혀 쓰이지 않는다.

예제 케이스 #3에서는 어떤 금속이 자기 자신을 만드는 데 사용될 수도 있음에 유의하라. (때로는 연금술의 법칙이 터무니없을 수도 있다!) 안타깝게도 이 경우에는 납을 전혀 만들 수 없다. 공식은 한 그램 단위에만 적용되므로, 예를 들어 2번 금속과 3번 금속을 각각 0.5그램 사용하여 4번 금속 0.5그램을 만든 다음, 3번 금속과 4번 금속을 각각 0.5그램 사용하여 납 0.5그램을 만들 수는 없음에 유의하라.