题目背景

与其编写苍白无力的背景，不如出更有质量的题。

题目描述

给定长度为 $n$ 的序列 $A$。

定义序列 $A$ 的某个子段 $[L,R]$ 的权值为:

$$\sum_{i=L}^{R}[\vert A_i - A_L \vert是完全平方数] \times \sum_{i=L}^{R}[\vert A_R - A_i \vert是完全平方数] $$

现在你需要将序列 $A$ 不重不漏地划分成若干个子段，使得对于 $\forall i \in [1,n]$，长度为 $i$ 的子段有 $c_i$ 个。

在此基础上，求一种划分方案使所有子段权值和最大，输出这个最大值即可。特殊地，若不存在任意一种划分方案，则输出 -1。

对题意不清楚的，可见下方说明提示。

输入格式

首先输入一个整数 $n$，表示序列 $A$ 的长度。

然后输入一行 $n$ 个数，其中第 $i$ 个数表示 $A_i$。

最后再输入一行 $n$ 个数，其中第 $i$ 个数表示 $c_i$。

输出格式

输出一行一个整数，表示答案。

6
2 1 4899 4 1 4
1 1 1 0 0 0

9

10
1 1 1 2 4 3 3 3 8 8
2 1 2 0 0 0 0 0 0 0

24

提示

样例解释

对于样例一，一种最优划分是分别在第二、三个数后面将序列断开。

对于样例二，一种最优划分是分别在第三、四、五、八个数后面将序列断开。

---

数据范围

「本题采用捆绑测试」

• $\operatorname{Subtask} 1(10\%)$：$n \leq 20$。

• $\operatorname{Subtask} 2(20\%)$：$n \leq 50,\sum_{i=1}^{n}c_i \leq 20$。

• $\operatorname{Subtask} 3(20\%)$：$n \leq 50,\forall i>5,c_i=0$。

• $\operatorname{Subtask} 4(50\%)$：无特殊限制。

对于 $100\%$ 的数据：$0 \leq c_i\leq n \leq 120,1 \leq a_i \leq 10^4$。

---

说明提示

• 我们规定，$0$ 是完全平方数。

• $[P]=1$ 当且仅当 $P$ 是真命题，否则 $[P]=0$。