
ZOJ Problem Set  4019
DreamGrid has a magical knapsack with a size capacity of \(c\) called the Schrödinger's knapsack (or Sknapsack for short) and two types of magical items called the Schrödinger's items (or Sitems for short). There are \(n\) Sitems of the first type in total, and they all have a value factor of \(k_1\); While there are \(m\) Sitems of the second type in total, and they all have a value factor of \(k_2\). The size of an Sitem is given and is certain. For the \(i\)th Sitem of the first type, we denote its size by \(s_{1,i}\); For the \(i\)th Sitem of the second type, we denote its size by \(s_{2,i}\). But the value of an Sitem remains uncertain until it is put into the Sknapsack (just like Schrödinger's cat whose state is uncertain until one opens the box). Its value is calculated by two factors: its value factor \(k\), and the remaining size capacity \(r\) of the Sknapsack just after it is put into the Sknapsack. Knowing these two factors, the value \(v\) of an Sitem can be calculated by the formula \(v = kr\). For a normal knapsack problem, the order to put items into the knapsack does not matter, but this is not true for our Schrödinger's knapsack problem. Consider an Sknapsack with a size capacity of 5, an Sitem with a value factor of 1 and a size of 2, and another Sitem with a value factor of 2 and a size of 1. If we put the first Sitem into the Sknapsack first and then put the second Sitem, the total value of the Sitems in the Sknapsack is \(1 \times (52) + 2 \times (31) = 7\); But if we put the second Sitem into the Sknapsack first, the total value will be changed to \(2 \times (51) + 1 \times (42) = 10\). The order does matter in this case! Given the size of DreamGrid's Sknapsack, the value factor of two types of Sitems and the size of each Sitem, please help DreamGrid determine a proper subset of Sitems and a proper order to put these Sitems into the Sknapsack, so that the total value of the Sitems in the Sknapsack is maximized. InputThe first line of the input contains an integer \(T\) (about 500), indicating the number of test cases. For each test case: The first line contains three integers \(k_1\), \(k_2\) and \(c\) (\(1 \le k_1, k_2, c \le 10^7\)), indicating the value factor of the first type of Sitems, the value factor of the second type of Sitems, and the size capacity of the Sknapsack. The second line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 2000\)), indicating the number of the first type of Sitems, and the number of the second type of Sitems. The next line contains \(n\) integers \(s_{1,1}, s_{1,2}, \dots, s_{1,n}\) (\(1 \le s_{1,i} \le 10^7\)), indicating the size of the Sitems of the first type. The next line contains \(m\) integers \(s_{2,1}, s_{2,2}, \dots, s_{2,m}\) (\(1 \le s_{2,i} \le 10^7\)), indicating the size of the Sitems of the second type. It's guaranteed that there are at most 10 test cases with their \(\max(n, m)\) larger than 100. OutputFor each test case output one line containing one integer, indicating the maximum possible total value of the Sitems in the Sknapsack. Sample Input3 3 2 7 2 3 4 3 1 3 2 1 2 10 3 4 2 1 2 3 2 3 1 1 2 5 1 1 2 1 Sample Output23 45 10 HintFor the first sample test case, you can first choose the 1st Sitem of the second type, then choose the 3rd Sitem of the second type, and finally choose the 2nd Sitem of the first type. The total value is \(2 \times (71) + 2 \times (62) + 3 \times (43) = 23\). For the second sample test case, you can first choose the 4th Sitem of the second type, then choose the 2nd Sitem of the first type, then choose the 2nd Sitem of the second type, then choose the 1st Sitem of the second type, and finally choose the 1st Sitem of the first type. The total value is \(2 \times (101) + 1 \times (91) + 2 \times (82) + 2 \times (63) + 1 \times (32) = 45\). The third sample test case is explained in the description. It's easy to prove that no larger total value can be achieved for the sample test cases. Author: CHEN, Shihan Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple 