Announcement
**Second Round will be ONLINE instead of ONSITE*****
Problem Statement

Schimdt is teaching Jenko a new technique to excel at bases. He writes n numbers in base k on a piece of paper and also their decimal sum. He doesn’t mention k on the paper. Jenko has to find out the value of k using those numbers and their sum. As Jenko is weak in maths, he needs your help to find the value of k.

Input

First line contains n, the count of numbers written on the paper. Next n lines contains the numbers in base k. Next line contains their decimal sum.

Output

Output the desired value of k. If multiple solutions are possible, print the minimum possible value.

Constraints

1 ≤ n ≤ 100000

2 ≤ k ≤ 16

Note: The decimal sum of all the numbers will never exceeds 10^18.

SAMPLE INPUT
2
10 21
10

SAMPLE OUTPUT
3

Explanation

10 in base 3=3 in base 10.
21 in base 3=7 in base 10.
Their sum is 3+7=10 which is given. So, 3 is the required answer

见题面

见题面