만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

하모닉 은신처

시간 제한1초메모리 제한1024 MB

요약
정확히 N개의 가전을 K종 중에서 고르고, 두 사람이 각자 선호하는 종류에서 M개 이상씩 골라 최소 비용을 구합니다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 수학
정답자
아직 제출이 없습니다

문제

한별이와 은하는 비밀 은신처를 만들기 위해 부동산 계약을 마쳤다. 두 사람은 은신처를 아늑하게 꾸미고 함께 시간을 보내며 즐길 수 있도록 가전제품을 사려고 한다. 제한된 은신처 공간에 정확히 NN개의 가전제품을 들여놓아야 한다.

가전 매장에는 KK종류의 가전제품이 있고, 종류마다 가격이 따로 정해져 있다. 한별이와 은하는 NN개의 가전제품을 가장 적은 비용으로 구하려고 한다.

아무거나 고를 수는 없다. 한별이는 AA종류의 가전제품을 선호하고, 은하는 BB종류를 선호한다. 두 사람의 선호가 겹칠 수도 있다. 타협을 위해 구매하는 NN개 중 최소 MM개는 한별이가 선호하는 종류여야 하고, 최소 MM개는 은하가 선호하는 종류여야 한다.

이 조건을 만족하도록 어떤 가전제품을 살지 정해 달라.

입력

첫 번째 줄에는 공백으로 구분된 두 정수 NN과 KK가 주어진다. NN은 은신처에 들어갈 수 있는 가전제품의 개수이고, KK는 매장에 있는 가전제품 종류의 수이다. (1≤N≤K≤300 0001 \le N \le K \le 300\,000)

두 번째 줄에는 공백으로 구분된 세 정수 MM, AA, BB가 주어진다. MM은 각자 선호하는 종류에서 반드시 사야 하는 가전제품의 최소 개수이고, AA는 한별이가 선호하는 종류의 수, BB는 은하가 선호하는 종류의 수이다. (1≤M≤A,B≤N1 \le M \le A,B \le N)

세 번째 줄에는 공백으로 구분된 KK개의 정수 c1,c2,⋯ ,cKc_1, c_2, \cdots, c_K가 주어진다. cic_i는 ii번째 종류의 가격이다. (1≤ci≤1091 \le c_i \le 10^9)

네 번째 줄에는 공백으로 구분된 AA개의 정수 a1,a2,⋯ ,aAa_1, a_2, \cdots, a_A가 주어진다. 한별이가 선호하는 종류의 번호이다. (1≤ai≤K1 \le a_i \le K; i≠j→ai≠aji \ne j \rightarrow a_i \ne a_j)

다섯 번째 줄에는 공백으로 구분된 BB개의 정수 b1,b2,⋯ ,bBb_1, b_2, \cdots, b_B가 주어진다. 은하가 선호하는 종류의 번호이다. (1≤bi≤K1 \le b_i \le K; i≠j→bi≠bji \ne j \rightarrow b_i \ne b_j)

출력

조건을 모두 만족하는 최소 총비용을 출력한다. 조건을 만족하는 선택이 없으면 -1을 출력한다.

예제2

  1. 예제 1

    입력
    3 5
    2 2 2
    3 1 4 1 5
    1 2
    1 2
    
    예상 출력
    5
    
  2. 예제 2

    입력
    3 5
    1 2 3
    3 1 4 1 5
    3 5
    1 2 4
    
    예상 출력
    6