站神的梦

抬头一看，站神来到了国际大学生程序设计竞赛中国区决赛（EC-Final）的现场，他直接选择AC最后一题。

对于一个集合{1, 2, …, n}的子集A，我们可以按照下面的方法计算子集A的分数。

1、起始分是0；

2、对于每个i属于A，A的分数加上ai；

3、对于任意的数对(i, j)满足i>= 2, j >= 2, i属于A并且j属于A，如果存在一个正数k>1满足i的k次方等于j，A的分数要减bj

找出子集A的最大可能分数。

注意程序要尽量运行的快一些哦，毕竟你就是下一个站神哦，奥里给~

第一行一个数n（1 <= n <= 100000）

第二行n个整数a1,a2,…,an(1 <= ai <= 1000000000)

第三行n个整数b1,b2,…,bn(1 <= ai <= 1000000000)

输入一个整数x，表示子集A的最大可能分数

第1组:
4
1 1 1 2
1 1 1 1

第2组:
4
1 1 1 1
1 1 1 2

第1组:
4

第2组:
3