
ZOJ Problem Set  3135
A college student JiSung has a roommate, YoungPyo, who shares a room with him in the dormitory. Since they have lived together for a long time, they also share household facilities, for example, a hair dryer, an electric iron, a battery charger, etc. So the time periods when they want to use one facility should not overlap. Some day, JiSung and YoungPyo both have a sequence of facilities o_{i1}, o_{i2}, ... , o_{in} and o_{j1}, o_{j2}, ... , o_{jm}, respectively, which they want to use in this order. Here a facility can be used more than once, that is, o_{ik} = o_{jl}, for some k, l. It takes p_{i}and q_{i} time units that JiSung and YoungPyo use the facility o_{i}, respectively. The problem is to minimize the finishing time by which they have used all facilities. For example, JiSung and YoungPyo share household facilities o_{1}, o_{2}, o_{3} which they use during 1, 2, 1 and 2, 1, 3 time units, respectively. At some day, they use the facilities o_{1}, o_{3}, o_{1}, o_{2} and o_{1}, o_{2}, o_{1}, o_{3} in order, respectively. Then the following figure represents the schedule which minimizes the finishing time. The minimum finishing time is 8 in this example. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given on the first line of the input. The first line of each test case contains an integer n, 1 <= n<= 50 , the number of facilities. The second and third line of each test case contain a sequence of n integers between 1 and 100, where the ith number, 1 <= i<= n, represents the number of time units during which JiSung and YoungPyo use the facility i, respectively. The fourth line of each test case contains two integer numbers α and β , 1 <= α , β <= 300 , the lengths of the sequences of facilities which JiSung and YoungPyo will use at the day, respectively. The fifth and sixth line of each test case contain a sequence of integers between 1 and n, representing a sequence of facilities which JiSung and YoungPyo will use in order at the day, respectively. Output Your program is to write to standard output. Print exactly one line for each test case. The line contains the minimum time by which both JiSung and YoungPyo finish to use all the facilities. Sample Input3 2 1 2 2 1 2 2 1 2 1 2 2 2 1 1 3 3 2 1 2 1 2 1 3 2 1 3 1 2 1 4 4 1 2 1 3 1 3 1 2Sample Output 4 6 8 Source: Asia Regional Contest Seoul 2006 