#1047. 选择美食

内存限制:512 MiB 时间限制:1000 ms 输入文件:food.in 输出文件:food.out
题目类型:传统 评测方式:文本比较
上传者: H6_6Q

题目描述

餐厅里有 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

输入格式

第一行输入一个整数 n ,表示一共有多少种美食。

接下来一行输入 n 个整数,第 i 个整数 a_i 表示第 i 种菜的美味值。

接下来一行输入 n 个整数,第 i 个整数 c_i 表示第 i 种菜的价格。

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

输出格式

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

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

样例

输入样例 #1:

3
2 4 1
5 3 2
1 8 0

输出样例 #1:

8

输入样例 #2:

4
2 3 7 4
3 4 1 2
1 24 0

输出样例 #2:

9

数据范围与提示

【样例解释】

对于样例 #1:

1^0 \times 8 =8 ,满足 \varphi\left(8 \right)=4\ |\ 8

选第 1 个美食和第 2 个美食得到的满意值恰好为 2 \times 4 =8

花费为 5+3 =8

【数据范围与约定】

对于全部的数据,满足 1 \le n \le 10^5 , 1 \le a_i,c_i \le 10^9 , 1 \le A,B \le 10^5 , 0 \le k \le 40

测试点编号 分值 n= d\le 特殊性质
1\sim3 15 10 10^5
4\sim6 10^9
7\sim10 20 100 10^{205}
11,12 10 10^5 保证所有 c_i 均为 1
13,14 保证数据随机
15\sim20 30