채점

\(N\)개의 문항이 있는 답안지를 채점하고자 한다. 1번부터 \(N\)번까지 각 문항에 대한 배점이 각각 \(S_{1}\), \(S_{2}\), ..., \(S_{N}\)일 경우, 문항별 점수와 답안지의 총점은 다음과 같이 결정된다.

• 틀린 문항에 대한 점수는 0이다.

• 1번 문항이 맞으면 이 문항의 점수는 \(S_{1}\)이다. \(i(2 \le i \le N)\)번 문항의 답이 맞을 경우에는 (\(i\)-1)번 문항의 정답 여부에 따라 이 문항의 점수가 다르게 정해진다.

• (\(i\)-1)번 문항의 답도 맞으면 \(i\)번 문항의 점수는 \(S_{i}\)에 (\(i\)-1)번 문항의 점수를 더한 값이 된다.

• (\(i\)-1)번 문항의 답이 틀리면 \(i\)번 문항의 점수는 \(S_{i}\)이다.

• 답안지의 총점은 위와 같이 계산된 문항별 점수의 합이다.

예를 들어 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 \le N \le 150)\)이 주어진다. 다음 줄에는 \(N\)개 문항들의 배점이 빈칸을 사이에 두고 차례대로 주어진다. 문항별 배점은 1 이상 100 이하의 정수이다. 마지막 줄에 자연수 \(K(1 \le K \le 2{,}000{,}000{,}000)\)가 주어진다.

답안지의 총점으로 나올 수 없는 가장 작은 정수 \(M(M \ge K)\)을 첫째 줄에 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2008 > 2차 대회 > 중등부 2번 / 고등부 1번