当你们一行人终于修好神社准备走时，幽幽子正好过来和灵梦商谈进货事宜。

由于幽幽子食量极大，每天都会云游很多地方去吃东西，于是在幻想乡各地都有VIP Credit（富婆）

正好你们一行人被灵梦薅光了，幽幽子想让你们计算一下进货的最优路线来节省成本 节省下来的钱给穿越三人发工资.jpg

幻想乡有 n 个地区，编号分别为 1\cdots n，当且仅当 j 能整除 i 时，地区 i 有通往地区 j 的单向的路。例如 2 有通向 4 的路，4 没有通向 2 的路，3,5 之间都没有通向对方的路。

地区 i 拥有幽幽子储备粮 k_i 箱，每箱储备粮的价值为 a_i。地区 i 有资金 b_i 元，若地区 j 可通向地区 i，则地区 j 可以调配物资给地区 i(注意不能自己调配给自己)，若调配 m 箱，则 i 地区需要支付运费 m^2 元。

现幽幽子会选定一个地区 x 去炫饭。若被选中，则地区 x 需要则该地区能够调用自己的所有 b_x 元资金，调配来总价值尽可能大的物资。

你需要算出，每个地区在不考虑自己原有的物资的总价值情况下，能够调配到最大的物资总价值，并输出这个最大值。

输入一行整数 ，代表地区数量 n(1\le n\le 300)。

接下来输入一行 n 个整数，第 i 个整数为 a_i(1\le a_i\le 10^9)。

接下来输入一行 n 个整数，第 i 个整数为 k_i(1\le k_i\le 300)。

接下来输入一行 n 个整数，第 i 个整数为 b_i(1\le b_i\le 300)。

输出一行一个整数，代表可调配的最大的物资总价值。

对样例一，选择地区 4，可以购买地区 1,2 的物资各一箱，运费为 1^2+1^2=2，总价值为 1+2=3。

对样例二，选择地区 4，可以购买地区 2 的物资两箱，运费为 2^2=4，总价值为 2\times 15=30。

对样例三，选择地区 4，可以购买地区 1,2 的物资各一箱，运费为 1^2+1^2=2，总价值为 10+15=25。