Maximizing Subsegment Weights Partition

Given an integer sequence (A) of length (n) and a multiset of segment counts (c_1, c_2, \dots, c_n), a partition of (A) is obtained by splitting (A) into contiguous subsegments that cover (A) with no overlap and no omission. In the partition, for every (i \in [1,n]), exactly (c_i) subsegments must have length (i). Note that the total number of elements covered is (\sum_{i=1}^{n} i,c_i); if this sum does not equal (n) then a valid partition does not exist.

For any subsegment ([L, R]) (using 1-indexing) of (A), define its weight as

[ W(L,R) = \left(\sum_{i=L}^{R} \mathbb{1}{|A_i - A_L| \text{ is a perfect square}}\right) \times \left(\sum_{i=L}^{R} \mathbb{1}{|A_R - A_i| \text{ is a perfect square}}\right), ]

where the indicator function (\mathbb{1}{P}) is 1 if property (P) holds and 0 otherwise, and a nonnegative integer (x) is a perfect square if there exists an integer (k \ge 0) such that (k^2 = x) (note that 0 is considered a perfect square).

The goal is to select an ordering of the segments (i.e. decide the lengths of segments in order over (A)) such that the entire sequence is partitioned and the sum of subsegment weights is maximized. Output the maximum possible sum of weights. If no valid partition exists, output -1.

inputFormat

The input is given via standard input and has the following format:

 n
 A1 A2 ... An
 c1 c2 ... cn

Here:

• \(n\) is the length of the sequence \(A\).
• The second line contains \(n\) integers representing the sequence \(A\).
• The third line contains \(n\) integers where the \(i\)th integer represents \(c_i\), i.e. the required number of subsegments of length \(i\). The sum \(\sum_{i=1}^{n} i\,c_i\) must equal \(n\) for a valid partition.

outputFormat

Output a single integer — the maximum sum of weights over all valid partitions of \(A\) satisfying the given segment length counts. If no valid partition exists, output -1.

sample

3
1 2 3
1 1 0

5