상자 공장

당신은 조립 라인이 두 개 있는 공장을 소유하고 있다. 첫 번째 조립 라인은 상자를 만들고, 두 번째 조립 라인은 그 상자에 넣을 장난감을 만든다. 각 상자 종류에는 한 종류의 장난감이 대응하며, 그 반대도 마찬가지이다.

처음에 첫 번째 조립 라인에서 상자 하나를 집고 두 번째 조립 라인에서 장난감 하나를 집는다. 그런 다음 몇 가지 선택을 할 수 있다.

• 언제든지 상자를 버리고 다음 상자를 집을 수 있다.

• 언제든지 장난감을 버리고 다음 장난감을 집을 수 있다.

• 상자와 장난감의 종류가 같다면 장난감을 상자에 넣어 고객에게 보낼 수 있다. 상자는 언제나 만들어진 순서대로 집으며, 장난감도 마찬가지이다. 상자와 장난감이 만들어지는 순서를 알고 있으며, 가능한 한 많은 상자에 담긴 장난감을 고객에게 보낼 수 있는 전략을 세우려고 한다.

경고: 두 조립 라인은 매우 많은 상자와 장난감을 만든다. 하지만 종류를 바꾸기 전까지 오랫동안 한 종류의 물건을 만드는 경향이 있다.

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 30초. 1 ≤ T ≤ 100. 1 ≤ $a_{i}$, $b_{i}$ ≤ $10^{16}$. 1 ≤ $A_{i}$, $B_{i}$ ≤ 100.

테스트 세트 1 (결과 공개)

1 ≤ N ≤ 3. 1 ≤ M ≤ 100.

테스트 세트 2 (결과 비공개)

1 ≤ N, M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 정수 N과 M이 담긴 줄로 시작한다. 이어서 2 * N개의 정수 $a_{1}$, $A_{1}$, $a_{2}$, $A_{2}$, ..., $a_{N}$, $A_{N}$이 담긴 한 줄과, 2 * M개의 정수 $b_{1}$, $B_{1}$, $b_{2}$, $B_{2}$, ..., $b_{M}$, $B_{M}$이 담긴 또 다른 한 줄이 주어진다.

이는 첫 번째 조립 라인이 $A_{1}$ 종류의 상자 $a_{1}$개를 만들고, 그다음 $A_{2}$ 종류의 상자 $a_{2}$개를 만드는 식으로 계속하여, 마지막으로 $A_{N}$ 종류의 상자 $a_{N}$개를 만든다는 뜻이다. 마찬가지로 두 번째 조립 라인은 $B_{1}$ 종류의 장난감 $b_{1}$개를 만들고, 이어서 $B_{2}$ 종류의 장난감 $b_{2}$개를 만드는 식으로 계속하여, 마지막으로 $B_{M}$ 종류의 장난감 $b_{M}$개를 만든다.

장난감과 상자는 종류 번호가 같을 때, 그리고 그럴 때에만 서로 짝지을 수 있다.

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 고객에게 보낼 수 있는 상자에 담긴 장난감 수의 최댓값이다.