상자 공장 (라지)

공장에 조립 라인이 두 개 있다. 첫 번째 라인은 상자를 만들고, 두 번째 라인은 그 상자에 담을 장난감을 만든다. 상자와 장난감에는 종류 번호가 붙어 있고, 종류 번호가 같은 상자와 장난감만 짝이 된다.

먼저 첫 번째 라인에서 상자를 하나 집고, 두 번째 라인에서 장난감을 하나 집는다. 그다음부터는 아래 동작을 원하는 만큼 반복한다.

• 들고 있는 상자를 버리고 다음 상자를 집는다.
• 들고 있는 장난감을 버리고 다음 장난감을 집는다.
• 상자와 장난감의 종류가 같으면 장난감을 상자에 넣어 고객에게 보내고, 다음 상자와 다음 장난감을 집는다.

상자는 만들어진 순서대로만 집을 수 있고, 장난감도 마찬가지다. 두 라인이 무엇을 어떤 순서로 만드는지는 미리 알고 있다. 고객에게 보내는 포장 완성품의 개수를 최대로 하는 전략을 세워서, 그 최대 개수를 구하라.

두 라인은 상자와 장난감을 아주 많이 만든다. 다만 한 종류를 오랫동안 만든 뒤에 다른 종류로 바꾸는 식이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $M$이 주어진다. 다음 줄에는 $2N$개의 정수 $a_1, A_1, a_2, A_2, \dots, a_N, A_N$이 주어지고, 그다음 줄에는 $2M$개의 정수 $b_1, B_1, b_2, B_2, \dots, 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 a_i, b_i \le 10^{16}$
• $1 \le A_i, B_i \le 100$
• $1 \le N, M \le 100$

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