33069번 - Harmonic Hideout 서브태스크다국어

문제

Hanbyeol and Eunha have finalized a real estate contract to create their secret hideout. They plan to shop for household appliances to make it both cozy for living and fun for spending time. They aim to fit exactly $N$ appliances into their limited hideout space.

They can choose from $K$ types of appliances at the appliance store, each with its own price. Hanbyeol and Eunha want to acquire $N$ appliances at the lowest possible cost.

However, they cannot simply choose any appliances. Hanbyeol prefers $A$ types of appliances, and Eunha prefers $B$ types. Their preferences may overlap. To reach a compromise, they have agreed that among the $N$ appliances, at least $M$ appliances must be from the types Hanbyeol prefers, and at least $M$ appliances must also be from the types Eunha prefers.

Please help Hanbyeol and Eunha decide which appliances to purchase under these conditions.

입력

The first line contains two space-separated integers: $N,ドル denoting the count of appliances that fit in the hideout, and $K,ドル denoting the count of the types of appliances that the appliance store has. (1ドル \le N \le K \le 300,000円$)

The following line contains three space-separated integers: $M,ドル denoting the minimum count of bought appliances that must be from the types favored by each girl; $A,ドル denoting the number of types that Hanbyeol prefers; and $B,ドル denoting the number of types that Eunha prefers. (1ドル\le M \le A,B \le N$)

The following line contains $K$ space-separated integers: $c_1,c_2, \cdots c_K$​, where $c_i$ denotes the cost of the $i$-th type of appliance that the store has. (1ドル \le c_i \le 10^9$)

The following line contains $A$ space-separated integers: $a_1,a_2,\cdots,a_A$​, denoting the index of appliances that Hanbyeol prefers. (1ドル \le a_i \le K;$ $i \ne j \rightarrow a_i \ne a_j$​)

The following line contains $B$ space-separated integers: $b_1,b_2,\cdots,b_B$​, denoting the index of appliances that Eunha prefers. (1ドル \le b_i \le K;$ $i\ne j \rightarrow b_i \ne b_j$​)

출력

Output the minimum cost to fulfill all constraints. If it is impossible, output -1 instead.

제한

서브태스크 1 (40점)

Modified constraints apply: 1ドル \le N \le K \le 16$.

서브태스크 2 (40점)

Modified constraints apply: 1ドル \le N \le K \le 300,000円;$ $\boldsymbol{\underline{M=A=B;}}$ $\boldsymbol{\underline{a=b,}},ドル i.e., what Eunha prefers is also preferred by Hanbyeol, and vice-versa.

서브태스크 3 (18점)

Modified constraints apply: 1ドル \le N \le K \le 1,000円$.

서브태스크 4 (2점)

Original constraints apply: 1ドル \le N \le K \le 300,000円$.

힌트