시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB82717712821.157%

문제

영훈이의 취미는 스티커 수집이다. 서로 다른 스티커가 N개가 있고, 모두 번호가 0번부터 N-1번까지 매겨져 있다. 각 스티커는 한 개뿐이다. 각 스티커의 가격과 가치가 주어진다. 그리고, 영훈이가 현재 가지고 있는 스티커도 주어진다.

이때, 영훈이는 스티커를 팔고 사는 행동을 반복해서 가지고 있는 스티커의 가치의 합이 적어도 K가 되게 하려고 한다.

영훈이가 처음에 돈이 얼마가 있어야 영훈이가 가지고 있는 스티커의 가치의 합이 적어도 K가 되는지를 구하시오. 가능한 돈이 한 개가 아니라면 가장 작은 값을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 32보다 작거나 같은 자연수이다. 둘째 줄에는 각 스티커의 가격이 주어진다. 셋째 줄에는 각 스티커의 가치가 주어진다. 넷째 줄에는 K가 주어진다. 다섯째 줄에는 영훈이가 현재 가지고 있는 스티커의 개수가 주어진다. 여섯째 줄에는 영훈이가 가지고 있는 스티커의 번호가 주어진다. 가격은 30,000,000보다 작거나 같은 자연수이고, 영훈이가 가지고 있는 스티커의 개수는 0보다 크거나 같고, N보다 작거나 같은 정수이다. K는 0보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다. 가치는 1 이상 30,000,000 이하의 정수이다.

영훈이가 가지고 있는 스티커의 수가 0인 경우 여섯번째 줄은 주어지지 않는다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

예제 입력 1

2
2 15
2 21
13
0

예제 출력 1

15

예제 입력 2

5
9 18 7 6 18
12 27 10 10 25
67
2
4 0

예제 출력 2

22

예제 입력 3

4
14 14 12 6
19 23 20 7
10
3
3 2 1

예제 출력 3

0

예제 입력 4

10
43 33 14 31 42 37 17 42 40 20
116 71 38 77 87 106 48 107 91 41
811
1
6

예제 출력 4

-1

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: kcm1700
  • 문제의 오타를 찾은 사람: klimmek55