시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1535 | 419 | 237 | 26.810% |
N개의 문항이 있는 답안지를 채점하고자 한다. 1번부터 N번까지 각 문항에 대한 배점이 각각 S1, S2, ..., SN일 경우, 문항별 점수와 답안지의 총점은 다음과 같이 결정된다.
예를 들어 9개 문항이 있는 시험에서 문항별 배점이 <표 1>과 같다고 하자.
문항 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
문항 배점 | 3 | 2 | 7 | 2 | 6 | 8 | 2 | 5 | 2 |
<표 1>
어떤 답안지에서 문항 1번부터 9번까지에 대하여 제출한 답이 맞는지(○) 혹은 틀린지(×)가 아래 <표 2>와 같다고 하자.
문항 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
문항 배점 | ○ | × | ○ | ○ | ○ | × | × | ○ | × |
<표 2>
그러면 문항별 점수는 다음 <표 3>과 같으므로 답안지의 총점은 39점이 된다.
문항 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
문항 배점 | 3 | 0 | 7 | 9 | 15 | 0 | 0 | 5 | 0 |
<표 3>
그러나 어떤 수는 결코 답안지의 총점으로 나올 수 없다. 예를 들어, 문항별 배점이 <표 1>과 같을 때, 각 문항에 대하여 어떤 답을 하더라도 73점의 총점을 받을 수는 없다.
문항별 배점과 어떤 자연수 K가 입력으로 주어진다. K보다 크거나 같은 정수로서 총점으로 나올 수 없는 가장 작은 값 M을 구하는 프로그램을 작성하시오.
첫째 줄에 전체 문항 수 N(1 ≤ N ≤ 150)이 주어진다. 다음 줄에는 N개 문항들의 배점이 빈칸을 사이에 두고 차례대로 주어진다. 문항별 배점은 1 이상 100 이하의 정수이다. 마지막 줄에 자연수 K(1 ≤ K ≤ 2,000,000,000)가 주어진다.
답안지의 총점으로 나올 수 없는 가장 작은 정수 M(M ≥ K)을 첫째 줄에 출력한다.
9 3 2 7 2 6 8 2 5 2 72
73