P16680 [CSPro 27] 高维亚空间超频物质变压缩技术

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

西西艾弗岛上有 $n$ 块黄金，人们希望把这些黄金打包运出去，于是他们给这些黄金依次编号为 $1, 2, \ldots, n$，第 $i$ 块黄金的体积为 $v_i$。 由于现在是 2202 年，人们掌握高维亚空间超频物质变压缩技术。具体来说，人们需要将这些黄金按编号划分为若干段，使得每段内的黄金编号连续，并且每块黄金属于恰好一段。这种变压缩技术可以将每一段黄金的体积变为一个常数 $L$，成本是 $(s - L)^2$，其中 $s$ 为这一段的黄金的体积之和。注意，并不要求必须有 $s \leq L$ 或者 $s > L$。一种划分方案的成本是每一段的成本之和。 但由于人们发明变压缩技术时受到了来自虚境神秘伟大存在的莫名低语的影响，第 $i$ 块黄金被赋予了一个神秘学质量 $m_i$，而变压缩技术要求每段内编号最大的黄金的神秘学质量严格递增。也就是说，假定顺次划分了 $k$ 段，每段内编号最大的黄金的神秘学质量依次是 $m'_1, \ldots, m'_k$，那么必须满足 $m'_1 < \cdots < m'_k$。 现在西西艾弗岛上的人们想知道，在满足上述条件的前提下，最小的成本是多少？注意到总是可以把所有的黄金都压成一段，因此满足上述条件的划分一定存在。 形式化地，给定 $n \in \mathbb{N}^+$, $L \in \mathbb{N}$, $\{v_i\}_{i=1}^n \subset \mathbb{N}$, $\{m_i\}_{i=1}^n \subset \mathbb{N}$ 求： $$\min F_n(\{b_i\}_{i=1}^n; \{v_i\}_{i=1}^n; L) \Big| \{b_i\}_{i=1}^n \in A_n(\{m_i\}_{i=1}^n) \quad \tag{*}$$ 其中： $$A_n(\{m_i\}_{i=1}^n) = \{\{b_i\}_{i=1}^n \in I_n(\{m_i\}_{i=1}^n) | \forall j \in [1, b_n), \Delta M_n(\{m_i\}_{i=1}^n; \{b_i\}_{i=1}^n; j) > 0\}$$ $$F_n(\{b_i\}_{i=1}^n; \{v_i\}_{i=1}^n; L) = \sum_{j=1}^{b_n} (L - \sum_{i=1}^n \delta(b_i - j) \cdot v_i)^2$$ 其中，$\delta: \Rightarrow 0, 1$ 为单位元函数，即：$\forall x \in \mathbb{R}$, $\delta(x) = \begin{cases} 1, \text{ 如果 } x = 0 \\ 0, \text{ 其它情况} \end{cases}$ 另外，有：$I_n(\{m_i\}_{i=1}^n) = \{\{b_i\}_{i=1}^n \subset \mathbb{N} | b_1 = 1 \land \forall i \in [1, n), (b_{i+1} - b_i) \in \{0, 1\}\}$ 以及 $\forall \{b_i\}_{i=1}^n \in I_n(\{m_i\}_{i=1}^n), j \in [1, b_n)$, 有： $$\Delta M_n(\{m_i\}_{i=1}^n; \{b_i\}_{i=1}^n; j) = m_{\max\{i \in [1, n] | b_i = j + 1\}} - m_{\max\{i \in [1, n] | b_i = j\}}$$ 容易验证： $$\forall \{b_i\}_{i=1}^n \in I_n(\{m_i\}_{i=1}^n), j \in [1, b_n], \{i \in [1, n] | b_i = j\} \neq \phi \land \max\{i \in [1, n] | b_i = j\} \in [1, n]$$ 因此 $\forall \{b_i\}_{i=1}^n \in I(\{m_i\}_{i=1}^n), j \in [1, b_n], m_{\max\{i \in [1, n] | b_i = j\}}$ 是良定义的，从而 $\forall \{b_i\}_{i=1}^n \in I_n(\{m_i\}_{i=1}^n), j \in [1, b_n], \Delta M_n(\{m_i\}_{i=1}^n; \{b_i\}_{i=1}^n; j)$ 是良定义的。 此外，易见 $\forall \{m_i\}_{i=1}^n \subset \mathbb{N}$, 总有 $\{1, 1, \ldots, 1\} \in A_n(\{m_i\}_{i=1}^n)$, 从而 $A_n(\{m_i\}_{i=1}^n) \neq \phi$, 因此 $(*)$ 式也是良定义的。 （注：如果你看不懂以上形式化定义也无妨，直接阅读上面的文字叙述题意即可。）

从标准输入读入数据。 第一行两个正整数 $n, L$； 接下来一行 $n$ 个正整数表示 $v_1, \ldots, v_n$； 接下来一行 $n$ 个正整数表示 $m_1, \ldots, m_n$。

输出到标准输出。 一行一个整数表示答案。

### 样例 1 解释 把第 1 块黄金划为一段，第 $2 \sim 3$ 块黄金划为一段。由于 $m_1 = 1 < m_3 = 2$，这么划分是符合要求的；又因为每一段黄金的体积之和都等于 2，因此无需代价。 另一种划分方案是把第 $1 \sim 3$ 块黄金划为一段，但这样需要 4 的代价；除此之外其余的划分方案都是不符合要求的。 形式化地，记 $v = \{v_i\}_{i=1}^n$，$m = \{m_i\}_{i=1}^n$。 可以验证： $$\begin{aligned} I_n(m) &= \{b_1 = \{1, 1, 1\}, b_2 = \{1, 1, 2\}, b_3 = \{1, 2, 2\}, b_4 = \{1, 2, 3\}\} \\ A_n(m) &= \{b_1, b_3\} \end{aligned}$$ $b_2 \notin A_n(m)$ 是由于，令 $j = 1 \in [1, 2)$，则 $j + 1 = 2 \in [1, 2]$，$M_n(m; b_2; j + 1) = m_3 = 2$，$M_n(m; b_2; j) = m_2 = 2$，而 $2 > 2$ 不成立。$b_4 \notin A_n(m)$ 是类似的，请自行验证。 又由于： $$\begin{aligned} F_n(b_1; v; 2) &= (2 - (1 \cdot v_1 + 1 \cdot v_2 + 1 \cdot v_3))^2 = 4 \\ F_n(b_3; v; 2) &= (2 - (1 \cdot v_1 + 0 \cdot v_2 + 0 \cdot v_3))^2 + (2 - (0 \cdot v_1 + 1 \cdot v_2 + 1 \cdot v_3))^2 = 0 \end{aligned}$$ 因此答案是 $0$。 ### 数据范围 ::cute-table{tuack} | 子任务编号 | $n$ | $\forall i \in [1, n], m_i = i$ | 子任务分值 | | :-: | :-: | :-: | :-: | | $1$ | $18$ | 否 | $10$ | | $2$ | $2\,000$ | ^ | $30$ | | $3$ | $10^5$ | 是 | ^ | | $4$ | ^ | 否 | ^ | 对于所有数据：$1 \leq n \leq 10^5$，$1 \leq v_i \leq 10^4$，$1 \leq m_i \leq n$，$1 \leq L \leq 10^9$，$(1 \leq i \leq n)$ ### 提示 请注意答案可能的取值范围。