Suminator

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Suminator is a very limited programming language. A program in this language is simply a sequence of nonnegative integers. The program is evaluated using a stack of nonnegative integers. Initially, the stack is empty. Trying to pop an element from an empty stack returns a zero. (Alternately, you can imagine that the stack already contains a sufficient number of zeros in the beginning.)  A Suminator program is evaluated using the following algorithm:  
for i = 0 to length(program) - 1 {
    if ( program[i] is 0) {
         Pop the top two elements from the stack, add them together
         and push the result to the top of the stack.
    } else {
         Push program[i] to the top of the stack.
    }
}
Pop the top element of the stack and print it.
  For example, when executing the program {1}, we first push the 1 to the stack, and then we print it. When executing the program {5,0,1,2,0}, we take the following steps:
We push the 5 to the top of the stack.
We pop the top two elements (5 and 0), add them together and push the result (5).
We push the 1 to the top of the stack.
We push the 2 to the top of the stack. At this moment, the stack contains the values 5, 1, and 2 (from bottom to top).
We pop the top two elements (2 and 1), add them together and push the result (3).
We print the top element of the stack: the number 3. Note that the stack also contains the value 5, which is ignored.
 You are given a vector program containing a Suminator program (a sequence of nonnegative integers),it\'s size is n, in which one of the elements of the sequence was changed to -1. You are also given a int wantedResult. Your task is to change the -1 back to a nonnegative integer X in such a way that the resulting program prints the number wantedResult. Return X. If there are multiple possible values of X, return the smallest one. If there is no way to make the program print wantedResult, return -1 instead.
Notes
-
The return value always fits into an int. This follows from the constraints and the nature of the problem.
Constraints
-
program will contain between 1 and 50 elements, inclusive.
-
Each element of program will be between -1 and 1000000000 (10^9), inclusive.
-
program will contain -1 exactly once.
-
wantedResult will be between 1 and 1000000000 (10^9), inclusive.

Input

 The first line is an integer n indicating the vector\'s size.then contains n integers.
netx line is wantedResult.

Output

 For each test case, please print the answer X.

Sample Input

3 7 -1 0
10
6 100 200 300 0 100 -1
600
8 -1 8 4 0 1 2 0 0
16

Sample Output

3
0
-1

Hint

 

Source