Grading

You are grading an answer sheet with $N$ questions. Question $i$ has point value $S_i$ for $i = 1, 2, \dots, N$. Each question's score and the total score of the sheet are determined by the following rules.

1. A wrong question scores $0$.
2. A correct question is scored as follows.
   • If question $1$ is correct, its score is $S_1$.
   • For a correct question $i$ ($2 \le i \le N$): if question $i-1$ is also correct, its score is $S_i$ plus the score of question $i-1$; if question $i-1$ is wrong, its score is $S_i$.
3. The total score of the sheet is the sum of all per-question scores.

In other words, within a run of consecutively correct questions the point values accumulate from the start of the run.

For example, suppose an exam has 9 questions whose point values are given in Table 1.

Table 1

Suppose that on some answer sheet, whether questions 1 through 9 are correct (○) or wrong (×) is as in Table 2.

Table 2

Then the per-question scores are as in Table 3, so the total score of the sheet is 39.

Table 3

However, some integers can never appear as the total score. For example, when the point values are those of Table 1, no combination of correct and wrong answers can make the total equal $73$.

Given the point values and a natural number $K$, write a program that finds the smallest integer $M$ that is at least $K$ and cannot appear as the total score of the answer sheet.

The first line contains the number of questions $N$ ($1 \le N \le 150$). The second line contains the point values of the $N$ questions in order from question 1, separated by spaces; each value is an integer between $1$ and $100$. The third line contains a natural number $K$ ($1 \le K \le 2{,}000{,}000{,}000$).

Print on the first line the smallest integer $M$ ($M \ge K$) that cannot appear as the total score of the answer sheet.