Aquarium decoration
Contest: Playrix Codescapes Cup (Codeforces Round 413, rated, Div. 1 + Div. 2)
Difficulty rating: 2500
Tags: data structures, greedy, two pointers

Arkady and Masha want to choose decorations for thier aquarium in Fishdom game. They have n decorations to choose from, each of them has some cost. To complete a task Arkady and Masha need to choose exactly m decorations from given, and they want to spend as little money as possible.

There is one difficulty: Masha likes some a of the given decorations, Arkady likes some b of the given decorations. Some decorations may be liked by both Arkady and Masha, or not be liked by both. The friends want to choose such decorations so that each of them likes at least k decorations among the chosen. Help Masha and Arkady find the minimum sum of money they need to spend.

Input format:
The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤ m ≤ n, 1 ≤ k ≤ n) — the number of decorations, how many decorations the friends should choose, how many decorations each of them should like among the chosen.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 109) — decorations costs.

The third line contains single integer a (1 ≤ a ≤ n) — the number of decorations liked by Masha. The fourth line contains a distinct integers x1, x2, ..., xa (1 ≤ xi ≤ n) — the ids of decorations liked by Masha.

The next two lines describe decorations liked by Arkady in the same format.

Output format:
Print single integer: the minimum sum of money the friends should spend to fulfill all constraints. If it is not possible, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the only possible variant to choose 3 decorations having all conditions satisfied is to choose decorations 1, 2, 3.

In the second example friends can choose decoration 4 instead of decoration 3, because this one is one coin cheaper.

In the third example it's not possible to choose 2 decorations in a way that both are liked by both Masha and Arkady.

Example input:
4 3 2
3 2 2 1
2
1 2
2
1 3

Example output:
7

Example input:
4 3 2
3 2 2 1
2
1 2
3
4 1 3

Example output:
6

Editorial:
Let's divide the decorations in four groups: that aren't liked by anybody (group 0), that are liked only by Masha (group 1), that are liked only by Arkady (group 2), that are liked by both (group 3). Sort each group by the cost. Then, it's obvious that in optimal solution we should take several (or 0) first elements in each group. Take a look at the group 3. It's easy to see that if we take x decorations from it, then we should take first k - x decorations from each of the groups 1 and 2. Let's call these decorations (x from the group 3 and k - x from each of the groups 1 and 2) obligatory, and let's call the other decorations free. If the number of obligatory decorations is less than m, we need to take several cheapest free decorations. It's easy to construct an O(n2) solution then: for each x we can construct the answer described in linear time and then choose minimum among these answers.
To speed up the algorithm, let's try all x from the minimum possible (it's easy to get it from integers k, m and groups 1 and 2 sizes), making transfers from x to x + 1. We should maintain the set of costs of free decorations, and let's also keep integer y, which is the number of free decorations that we should add to the current answer, and also the sum of the y cheapest free decorations. When we increase x by 1, in groups 1 and 2 the most expensive obligatory decoration becomes free (because the value k - x decreases by one 1). These decorations (if any) we should add to our free set. We should also add one obligatory decoration from the group 3, so, the number of free decorations could change by one. So, we need at most 2 operations of adding an integer to a set, and an operation that changes y with the corresponding change of the sum. We can perform these operations in O(log(n)), for example, using two std::set objects in С++ (or its analogues in other languages) one set for the smallest y integers and one for the others. The overall complexity to change x to x + 1 is now O(log(n)), so the overall complexity is O(n * log(n)).