8952번 - Roommate 다국어채점 준비 중

문제

A college student Ji-Sung has a roommate, Young-Pyo, 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, Ji-Sung and Young-Pyo 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_il, for some k, l. It takes p_i and q_i time units that Ji-Sung and Young-Pyo use the facility o_i , respectively. The problem is to minimize the finishing time by which they have used all facilities.

For example, Ji-Sung and Young-Pyo share household facilities o₁, o₂, o₃, which they use during 1, 2, 1 and 2, 1, 3 time units, respectively. At some day, they use the facilities o₁, o₃, o₁, o₂ and o₁, o₂, o₁, o₃ in order, respectively. Then the following figure represents the schedule which minimizes the finishing time. The minimum finishing time is 8 in this example.

Ji-Sung :

Young-Pyo :

입력

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 i -th number, 1 ≤ i ≤ n, represents the number of time units during which Ji-Sung and Young-Pyo 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 Ji-Sung and Young-Pyo 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 Ji-Sung and Young-Pyo will use in order at the day, respectively.

출력

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 Ji-Sung and Young-Pyo finish to use all the facilities.

The following shows sample input and ouput for three test cases.

제한

힌트