404411: GYM101502 C Ahmad and Spells

Ahmad has recently started playing a new game called DotA (Defense of the Agents), which is a very interesting computer game, and currently he is learning a new strategy for winning with his special hero "Chimpanzee King". In order to perform the strategy, the hero must execute n spells.

Initially, each spell needs x seconds of channeling to be executed, but Ahmad knows two ways that can reduce the channeling time, which are:

1. There are m talents (the hero can learn no more than one talent), the i^th of them costs b_i mana-points, and changes the channeling time of all spells to a_i instead of x.
2. He can ask for help from other heroes (no more than one) to immediately execute spells. There are k such heroes, and the i^th of them costs d_i mana-points, and instantly executes c_i spells.

The total number of mana-points that Ahmad spends should not exceed s.

Ahmad wants to use this strategy at its best, so he is interested in the minimum time he needs to spend in order to execute n spells.

The first line of the input contains an integer T, where T is the number of test cases.

The first line of each test case contains three integers n, m, and k (1 ≤ n ≤ 2 × 10⁹, 1 ≤ m, k ≤ 10⁵), where n is the number of spells Ahmad has to execute, m is the number of talents, and k is the number of heroes.

The second line of each test case contains two integers x and s (2 ≤ x ≤ 2 × 10⁹, 1 ≤ s ≤ 2 × 10⁹), where x is the initial number of seconds required to channel one spell, and s is the number of mana-points Ahmad can use.

The third line of each test case contains m integers a₁, a₂, ..., a_m (1 ≤ a_i ≤ x), where a_i is the number of seconds it will take to prepare one potion of the i^th spell from the first type.

The fourth line of each test case contains m integers b₁, b₂, ..., b_m (1 ≤ b_i ≤ 2 × 10⁹), where b_i is the number of required mana-points to use the i^th spell from the first type.

The fifth line of each test case contains k integers c₁, c₂, ..., c_k (1 ≤ c_i ≤ n), where c_i is the number of potions that will be immediately created if the i^th spell from the second type was used.

The sixth line of each test case contains k integers d₁, d₂, ..., d_k (1 ≤ d_i ≤ 2 × 10⁹), where d_i is the number of mana-points required to use the i^th spell from the second type.

For each test case, print a single line containing the minimum time Ahmad has to spend in order to prepare n potions.

2
20 3 2
10 99
2 4 3
20 10 40
4 15
10 80
20 3 2
10 99
2 4 3
200 100 400
4 15
100 800

20
200

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.