#1202. zxh挑选生日礼物

Sheauhaw 决定给 Zeondik 赠送生日礼物！

现在 Sheauhaw 有 $n$ 个礼物可供选择, 在店员宫本茂 (Miyamizu) 的带领下, 有了初选方案. 这些礼物分别有标号 $1,2,\cdots,n$. 现在 Sheauhaw 决定选择其中一些礼物打包在一起, 作为 Zeondik 的生日礼物.

打包后的礼物包可以为 Zeondik 提供一些快乐值, 计算方法如下:

1. 空礼物包只包含祝福语和包装, 快乐值是 $A$.
2. 礼物包里如果包含了 $i$ 号礼物, 那么会额外带来 $a_i$ 点快乐值.
3. 套算一次原则: 礼物包里如果同时包含了 $i,j$ 号礼物, $i,j>1$, 且存在一个正整数 $k>1$ 满足 $i^k=j$, 那么就会执行一次修正.
4. 对于 $i,j$ 号有序礼物对带来的套算一次原则的修正, 效果是礼物包减少 $b_j$ 点快乐值.

现在, Sheauhaw 当然想让 Zeondik 获得尽可能多的快乐值. 请告诉 Sheauhaw 可能的最大的快乐值.

第一行两个整数 $n,A$, 表示可供选择的礼物数量, 和礼物包的快乐值.

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$, 表示第 $i$ 个礼物能带来的快乐值.

第三行 $n$ 个整数 $b_1,b_2,\cdots,b_n$, 表示第 $i$ 个礼物由套算一次原则带来的修正.

一行一个整数 $x$, 表示能达到的最大的快乐值.

样例输入

4 0
1 1 1 2
1 1 1 1

样例输出

4

$1\le n\le100000$

$-10^9\le A\le10^9$

$-10^9\le a_1,a_2,\cdots,a_n\le10^9$

$-10^9\le b_1,b_2,\cdots,b_n\le10^9$