시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 69 12 12 35.294%

문제

영훈이의 취미는 스티커 수집이다. 서로 다른 스티커가 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 이하의 정수이다.

 

출력

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

예제 입력

2
2 15
2 21
13
0

예제 출력

15

힌트

출처

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