912_E. Prime Gift_9734
Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of n distinct prime numbers alongside with a simple task: Oleg is to find the k-th smallest integer, such that all its prime divisors are in this set. 

Input

The first line contains a single integer n (1 ≤ n ≤ 16).

The next line lists n distinct prime numbers p1, p2, ..., pn (2 ≤ pi ≤ 100) in ascending order.

The last line gives a single integer k (1 ≤ k). It is guaranteed that the k-th smallest integer such that all its prime divisors are in this set does not exceed 1018.

Output

Print a single line featuring the k-th smallest integer. It's guaranteed that the answer doesn't exceed 1018.

Examples

Input

3
2 3 5
7


Output

8


Input

5
3 7 11 13 31
17


Output

93

Note

The list of numbers with all prime divisors inside {2, 3, 5} begins as follows:

(1, 2, 3, 4, 5, 6, 8, ...)

The seventh number in this list (1-indexed) is eight.
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x;
}
const int N = 63;
int n, cnt;
long long a[N], c[N], k, l, r;
vector<long long> s[2];
void dfs(int i, int x, long long now) {
  s[i].push_back(now);
  for (register int j = x; j <= cnt; ++j)
    if (1e18 / c[j] >= now) dfs(i, j, now * c[j]);
}
long long solve(long long x) {
  int j = 0;
  long long tot = 0;
  for (register int i = s[0].size() - 1; i >= 0; --i) {
    while (j < s[1].size() && s[1][j] <= x / s[0][i]) ++j;
    tot += j;
  }
  return tot;
}
int main() {
  n = read();
  for (register int i = 1; i <= n; ++i) a[i] = read();
  sort(a + 1, a + n + 1);
  scanf("%lld", &k);
  cnt = 0;
  for (register int i = 1; i <= n; ++i)
    if (i & 1) c[++cnt] = a[i];
  dfs(0, 1, 1);
  cnt = 0;
  for (register int i = 1; i <= n; ++i)
    if (!(i & 1)) c[++cnt] = a[i];
  dfs(1, 1, 1);
  sort(s[0].begin(), s[0].end());
  sort(s[1].begin(), s[1].end());
  l = 1, r = 1e18;
  while (l + 1 < r) {
    long long mid = (l + r) >> 1;
    if (solve(mid) >= k)
      r = mid;
    else
      l = mid + 1;
  }
  if (solve(l) >= k)
    printf("%lld\n", l);
  else
    printf("%lld\n", r);
  return 0;
}

3
2 3 5
7
 5
3 7 11 13 31
17
 1
83
6
 7
3 19 37 43 47 73 83
32338
 12
2 5 7 11 23 29 31 53 61 67 83 89
11925984
 2
3 7
406
 5
5 7 17 19 23
19838
 16
2 3 5 7 11 23 29 31 37 41 47 53 59 61 67 71
48452906
 12
3 5 7 13 17 19 31 37 61 79 83 97
8046630
 5
5 7 13 23 29
20345
 12
2 3 7 11 19 29 31 53 59 73 83 97
14165113
 8
3 7 13 17 29 41 43 47
430196
 12
3 11 17 19 23 29 47 53 59 67 71 79
37764
 7
2 11 13 19 41 59 73
48718
 16
2 3 5 11 13 23 29 31 37 47 53 73 79 83 89 97
95494812
 2
41 61
66
 16
2 3 5 7 11 13 17 23 29 31 37 41 47 53 59 67
1
 1
23
4
 1
19
4
 2
11 17
26
 12
3 19 23 29 31 37 43 59 67 73 79 89
1480623
 2
11 13
156
 16
2 3 5 7 11 17 19 29 31 47 53 67 71 73 83 89
315508919
 5
5 13 19 23 29
673
 16
3 5 7 11 13 37 41 43 47 59 61 67 73 83 89 97
59619226
 1
13
17
 7
2 5 37 41 53 59 73
78513
 7
2 3 5 7 13 37 97
200297
 5
2 5 7 23 29
28386
 5
5 7 11 17 23
15658
 12
2 5 7 13 19 23 31 37 41 79 89 97
10850747
 7
3 17 19 23 31 41 43
103787
 7
5 11 23 41 47 67 89
21642
 2
2 17
292
 1
2
36
 16
2 5 13 17 23 31 37 43 53 59 61 67 73 83 89 97
14029265
 1
5
1
 1
11
7
 8
2 3 5 7 11 13 19 23
4404338
 3
11 19 29
546
 5
3 5 7 11 29
9727
 8
2 3 7 11 17 19 23 29
2573899
 8
2 3 11 13 17 19 23 29
1609968
 16
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
1
 2
2 3
781
 5
2 7 13 17 19
1893
 16
2 5 7 11 13 19 23 29 37 41 59 61 67 83 89 97
156644145
 8
3 7 13 17 19 29 31 37
68830
 7
2 3 5 7 11 13 17
2666471
 9
2 3 7 13 17 19 29 31 37
2353167
 5
3 17 19 23 29
14598
 12
3 5 7 11 17 41 47 59 61 71 73 97
2487564
 5
3 5 7 11 29
18047
 12
5 17 23 31 41 47 53 61 67 71 89 97
1498107
 8
2 3 5 7 11 13 23 29
4014725
 12
3 5 11 17 19 23 43 59 73 79 83 89
2639765
 2
7 13
115
 16
2 7 17 19 23 31 41 43 59 61 71 73 79 83 89 97
35791394
 16
7 19 31 37 41 43 47 53 59 61 71 73 79 83 89 97
2997553
 7
11 13 19 31 47 83 97
47564
 16
3 5 13 17 29 37 41 43 47 53 59 67 71 73 83 97
39768007
 7
3 29 43 47 53 67 83
16352
 8
3 7 11 17 19 23 37 43
528714
 10
5 7 13 17 19 29 31 37 41 43
1675780
 16
3 5 11 13 17 37 41 47 53 59 61 67 73 79 89 97
7541983
 1
3
27
 11
2 3 13 17 19 23 29 31 37 41 47
1057708
 16
3 11 13 17 19 31 37 47 53 59 61 71 73 79 89 97
17713810
 16
3 5 7 17 19 29 31 37 43 61 67 71 73 83 89 97
52018960
 1
7
5
 12
2 3 5 13 17 29 31 37 47 67 73 89
8871760
 16
2 7 11 13 19 29 31 43 47 53 61 67 71 73 83 89
62457792
 5
5 11 17 23 29
4311
 12
2 3 7 11 13 19 29 31 41 43 47 53
19281646
 8
2 5 7 19 29 31 37 41
912071
 2
13 29
23
 16
2 3 7 11 13 17 19 23 29 31 37 43 47 53 61 71
175211930
 1
2
55
 16
2 3 5 7 11 13 19 23 29 31 37 53 59 61 67 79
342035643
 16
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
755104793
 1
77
6
 5
5 7 17 19 23
7186
 12
2 3 7 17 19 29 31 53 59 73 83 97
14165113
 8
3 7 13 17 29 41 43 45
430196
 7
3 11 13 19 41 59 73
48718
 2
41 63
66
 1
6
4
 1
33
4
 2
5 17
26
 7
4 5 37 41 53 59 73
78513
 7
2 3 5 7 13 37 97
33077
 5
6 7 11 17 23
15658
 7
3 8 19 23 31 41 43
103787
 1
3
7
 3
17 19 29
546
 2
2 3
491
 9
2 3 7 13 17 19 29 31 37
4347818
 12
3 10 11 17 19 23 43 59 73 79 83 89
2639765
 2
7 25
115
 1
3
38
 1
11
5
 12
2 3 7 11 13 19 22 31 41 43 47 53
19281646
 2
18 29
23
 16
2 3 5 7 11 13 19 23 29 31 37 53 59 61 67 79
340529745
 5
3 7 11 13 54
17
 1
78
6

8
 93
 3939040643
 3183280950920513
 301419849067832000
 272393967761220627
 127360414660865575
 804126613807440
 173676038924316695
 204919965537148225
 127001325888007494
 305676371111846553
 3927810717
 37312888001077
 42119814060080640
 550329031716248441
 1
 12167
 6859
 10106041
 50150550157338149
 705954940631245019
 718343216190308352
 138452525
 598041285733749375
 665416609183179841
 1719827640625000
 7595621495280
 148961113306250
 3573226485213841
 107689592768850176
 118287859814130519
 342762156070895
 84404697300992
 34359738368
 2418289423929800
 1
 1771561
 96144227557297920
 48364216424306959
 394292863125
 222801765143150592
 52272636008333312
 1
 385610460475392
 53202877
 991529674686751655
 2476061307629
 810722946966732800
 5633116276150272
 23610090783396093
 2365312425520625
 25488555332625
 549909223796509595
 100966044983345542
 8558183944012725
 51676101935731
 307958802673248128
 11399640607831889
 803966969563403789
 749475594623822625
 108423251809029
 139155272849176437
 352388344647077375
 703144305621225
 2541865828329
 7257035596446
 80800214839016049
 534530840244760065
 2401
 4695900205082112
 472958488994763772
 5920384757045
 32820959594794371
 116333178429440000
 20511149
 61877301658877952
 18014398509481984
 237003531345504000 1000000000000000000 2706784157
 30651325856179
 227315530657301832
 290108843746369557
 489410407312299
 640986380431006743
 216
 35937
 417605
 135291037611424000
 1735458816
 8006728345427658
 20266353800298072
 729
 458170386505397603
 297538935552
 151366970380222464
 31782814814470030
 2384185791015625
 450283905890997363
 14641
 25451222794506432
 54797472
 233083120182932250
 99
 2887174368
