상자 공장 (스몰)

조립 라인이 두 개인 공장을 운영한다. 첫 번째 라인은 상자를 만들고, 두 번째 라인은 그 상자에 담을 장난감을 만든다. 상자 종류마다 담을 수 있는 장난감 종류가 하나로 정해져 있고, 그 반대도 마찬가지다.

처음에 첫 번째 라인에서 상자 하나를, 두 번째 라인에서 장난감 하나를 집는다. 상자와 장난감을 하나씩 들고 있는 상태에서 다음 중 하나를 할 수 있다.

• 들고 있는 상자를 버리고 다음 상자를 집는다.
• 들고 있는 장난감을 버리고 다음 장난감을 집는다.
• 상자와 장난감의 종류가 같으면 장난감을 상자에 담아 손님에게 보낸다.

상자는 만들어진 순서대로 집고, 장난감도 만들어진 순서대로 집는다. 두 라인의 생산 순서를 알고 있을 때, 손님에게 보낼 수 있는 포장된 장난감의 최대 개수를 구한다.

두 라인은 상자와 장난감을 아주 많이 만든다. 다만 한 종류를 오랫동안 만든 뒤에야 다른 종류로 바꾸므로, 생산 순서는 같은 종류가 연달아 이어지는 구간 단위로 주어진다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

첫째 줄에 두 정수 $N$과 $M$이 주어진다. 둘째 줄에 $2N$개의 정수 $a_1$, $A_1$, $a_2$, $A_2$, ..., $a_N$, $A_N$이 주어진다. 셋째 줄에 $2M$개의 정수 $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_M$인 장난감 $b_M$개까지 만든다. 장난감은 종류 번호가 같은 상자에만 담을 수 있다.

인접한 두 구간의 종류 번호가 같을 수도 있다.

제한

• $1 \le T \le 100$
• $1 \le N \le 3$
• $1 \le M \le 100$
• $1 \le a_i, b_i \le 10^{16}$
• $1 \le A_i, B_i \le 100$

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 손님에게 보낼 수 있는 포장된 장난감의 최대 개수다.