餐厅里有 $n$ 种美食，每种美食都有一个美味值 $a_i$ 和价格 $c_i$ ，小 P 可以选择任意个美食，且每一种美食可以选择多次。

若小 P 选择的美食的编号为 $b_1\ ,\ b_2\ ...\ b_m$，则小 P 能得到的满意值则为 $\prod\limits_{i=1}^ma_{b_i}$

现在小 P 想要使他得到的满意值恰好为 $d$ ，请你告诉他最少需要花费多少钱。

由于小 P 的口味非常独特，所以他给出的 $d$ 一定满足 $\varphi\left(d\right)\ |\ d$。

由于小 P 非常不容易满足，故 $d$ 将有可能非常大，为了方便表示，小 P 会告诉你三个数 $A , B , k$ ，那么 $d = A^k \times B$ 。

$\varphi(d)$为欧拉函数，不清楚的同学可以查找一下相关资料

第一行输入一个整数 $n$。

接下来一行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来一行输入 $n$ 个整数，第 $i$ 个整数表示 $c_i$。

第四行输入三个整数 $A,B,k$ ，则小 P 想要的满意值 $d=A^k \times B$。

输出一个整数表示要使满意值恰好为 $d$ 则需要的最小花费。

若无论怎样选择都无法使满意值恰好为 $d$，则输出 -1 。

3
2 4 1
5 3 2
1 8 0

8

对于15%的数据，满足$n \le 10, d \le 10^5$

对于30%的数据，满足$n \le 10, d \le 10^9$

对于50%的数据，满足$n \le 100, d \le 10^{201}$

对于另外10%的数据，满足$c_i=1$

对于另外10%的数据，满足所有数据都在合法范围内等概率随机

对于全部数据，满足$1 \le n \le 10^5, 1 \le a_i \le 10^9, 0 \le c_i \le 10^9, 1 \le A,B \le 10^5, 0 \le k \le 30$且$\varphi(d)|d$