题目描述

You own a factory with two assembly lines. The first assembly line makes boxes, and the second assembly line makes toys to put in those boxes. Each type of box goes with one type of toy and vice-versa.

At the beginning, you pick up a box from the first assembly line and a toy from the second assembly line. You then have a few options.

• You can always throw out the box and pick up the next one.
• You can always throw out the toy and pick up the next one.
• If the box and toy are the same type, you can put the toy in the box, and send it out to customers.

You always pick boxes up in the order in which they are made, and similarly for toys. You know the order in which boxes and toys are made, and you want to plan out a strategy that will allow you to send as many boxed toys as possible to customers.

Warning: The two assembly lines make a lot of boxes and toys. However, they tend to make one kind of thing for a long period of time before switching.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case begins with a line containing two integers $N$ and $M$. It is followed by a line containing $2 \times N$ integers $a_1, A_1, a_2, A_2, ..., a_N, A_N$, and another line containing $2 \times M$ integers $b_1, B_1, b_2, B_2, ..., b_M, B_M$.

This means that the first assembly line will make $a_1$ boxes of type $A_1$, then $a_2$ boxes of type $A_2$, etc., until it finishes with $a_N$ boxes of type $A_N$. Similarly, the second assembly will make $b_1$ toys of type $B_1$, followed by $b_2$ toys of type $B_2$, etc., until it finishes with $b_M$ toys of type $B_M$.

A toy can be matched with a box if and only if they have the same type number.

输出格式

For each test case, output one line containing "Case #x: y", where $x$ is the case number (starting from 1), and $y$ is the largest number of boxed toys that you can send out to customers.

4
3 3
10 1 20 2 25 3
10 2 30 3 20 1
3 5
10 1 6 2 10 1
5 1 3 2 10 1 3 2 5 1
3 5
10 1 6 2 10 1
5 1 6 2 10 1 6 2 5 1
1 1
5000000 10
5000000 100

Case #1: 35
Case #2: 20
Case #3: 21
Case #4: 0

提示

Limits

• $1 \leq T \leq 100.$
• $1 \leq a_i, b_i \leq 10^{16}.$
• $1 \leq A_i, B_i \leq 100.$

Test set 1 (12 Pts, Visible Verdict)

• $1 \leq N \leq 3.$
• $1 \leq M \leq 100.$

Test set 2 (23 Pts, Hidden Verdict)

• $1 \leq N, M \leq 100.$