채점

$N$개의 문항으로 이루어진 답안지를 채점한다. 1번부터 $N$번까지 각 문항의 배점이 각각 $S_1, S_2, \dots, S_N$일 때, 문항별 점수와 답안지의 총점은 다음 규칙으로 정해진다.

1. 틀린 문항의 점수는 $0$이다.
2. 맞힌 문항의 점수는 다음과 같이 정한다.
   • 1번 문항을 맞히면 점수는 $S_1$이다.
   • $i$번 문항($2 \le i \le N$)을 맞혔을 때, ($i-1$)번 문항도 맞혔다면 점수는 $S_i$에 ($i-1$)번 문항의 점수를 더한 값이고, ($i-1$)번 문항을 틀렸다면 점수는 $S_i$이다.
3. 답안지의 총점은 이렇게 계산한 문항별 점수의 합이다.

즉, 연속해서 맞힌 구간에서는 구간의 처음부터 배점이 누적된다.

예를 들어 9개 문항이 있는 시험에서 문항별 배점이 <표 1>과 같다고 하자.

<표 1>

어떤 답안지에서 1번부터 9번 문항까지 제출한 답이 맞았는지(○) 틀렸는지(×)가 <표 2>와 같다고 하자.

<표 2>

그러면 문항별 점수는 <표 3>과 같고, 답안지의 총점은 39점이 된다.

<표 3>

한편, 어떤 정수는 답안지의 총점으로 결코 나올 수 없다. 예를 들어 배점이 <표 1>과 같을 때는, 각 문항을 어떻게 맞히거나 틀리더라도 총점이 $73$점이 될 수 없다.

문항별 배점과 자연수 $K$가 주어질 때, 답안지의 총점으로 나올 수 없는 정수 중에서 $K$ 이상인 가장 작은 값 $M$을 구하는 프로그램을 작성하시오.

첫째 줄에 문항 수 $N$($1 \le N \le 150$)이 주어진다. 둘째 줄에는 $N$개 문항의 배점이 공백으로 구분되어 1번 문항부터 차례대로 주어진다. 각 배점은 $1$ 이상 $100$ 이하의 정수이다. 셋째 줄에 자연수 $K$($1 \le K \le 2{,}000{,}000{,}000$)가 주어진다.

답안지의 총점으로 나올 수 없는 정수 중에서 $K$ 이상인 가장 작은 정수 $M$을 첫째 줄에 출력한다.