3946：Philosophy Girl’s Trail

  Philosophy Girl Krolia was always on the go. No one could figure out where she was. It’s said that she traveled all over the world with only two kinds of items:books and staffs.
  Krolia had a knapsack which is composed of n*m grids, and every item can be fit into grids. All the books’ size is 1*2(2*1), and the staffs’ is 1*3(3*1) and each of them can be rotated 90, 180 or 270 degrees. Every item is assigned a value and Krolia wanted to go with the maximal value.

  The first line comes with one integer T (T=100) which denotes the test cases.
  In the first line of each case, there is four integers n (1<=n<=500), m (1<=m<=500), n1 (1<=n1<=10000) and n2 (1<=n2<=10000) which indicates the size of the knapsack, the number of the optional books and staffs.
  The next line contains n1 integers which indicate the value bi (0<=bi<=1000) of every book.
  The last line contains n2 integers si (0<=si<=1000) which indicate the value of every staff.

  For each test case, output one line.
  First, output "Case #C: ", where C is the number of test case, from 1 to T. Then output the maximal value.