C Programming Language (Code With C Programming Language)

Problem Title: Magic Potion Jojo is the best chemist in the city. One day, a customer ask Jojo to create a magic potion. After days of research, Jojo finally found formula for magic potion. A magic potion can be created by combining exactly one bottle of potion A, exactly one bottle of potion B, and exactly one bottle of potion C regardless the composition ratio. So, if Jojo has X liter bottle of potion A, Y liter bottle of potion B, and Z liter bottle of potion C, once he combines it, he has to use the entire bottle and he will get X + Y + Z liter of magic potion.

One day, a customer ask for K liter of magic potion. Jojo immediately look at his shelves of potion. At shelf A, he has N_A bottles of potion A (each bottle has different capacity). The i-th bottle of potion A has A_i liter capacity. At shelf B, he has N_B bottles of potion B (each bottle has different capacity). The i-th bottle of potion B has B_i liter capacity. At shelf C, he has N_C bottles of potion C (each bottle has different capacity). The i-th bottle of potion C has C_i liter capacity. Jojo wants to know how many ways he can create K liter of magic potion. Remember that he can only use exactly one bottle and use the entire bottle of each potion type.

Format Input

There are T testcases. Every testcase consists of a line of an integer N_A followed by a line of N_A integers A₁, A₂, ..., A_NA. Followed by a line of an integer N_B followed by a line of N_B integers B₁, B₂, ..., B_NB. Followed by a line of an integer N_C followed by a line of N_C integers C₁, C₂, ..., C_NC . And finally followed by a line consists of an integer K.

Format Output

Output T testcases with format Case #X: , where X indicates the testcase number and then followed by an integer indicates how many ways Jojo can create K liter of magic potion.

Constraints

1 T 5 1 N_A, N_B, N_C 1000 1 A_i, B_i, C_i, K 10⁹

Sample Input (Standard Input)

3 3 1 2 3 3 3 2 1 3 5 1 3 7 5 1 3 7 10 9 4 2 5 12 8 3 13 23 22 100 3 2 3 5 3 3 5 2 3 5 2 3 10 Sample Output (Standard Output) Case #1: 5 Case #2: 0 Case #3: 6

Explanation:

At the first case, there are 5 ways to create 7 liter of magic potion: {A₁, B₁, C₃}, {A₁, B₃, C₁}, {A₂, B₂, C₃}, {A₃, B₁, C₂}, {A₃, B₃, C₃}.

At the second case, there are no ways to create 100 liter of magic potion.

At the first case, there are 6 ways to create 10 liter of magic potion: {A₁, B₁, C₁}, {A₁, B₂, C₃}, {A₂, B₂, C₂}, {A₂, B₃, C₁}, {A₃, B₁, C₂}, {A₃, B₃, C₃}. Note : Use Simple Code, please make 2 version, using bubble sort and using quicksort/mergesort, Using Standard C Language