题目描述

在《机械设计与制作》课程中，Jimmy 制作了一款机械臂作为期末作业。在测试与改进阶段，immy 通过实验测得了他设计的机械臂的尺寸、硬度、灵活度、最大抓力等 $n$ 个参数 $A_1, A_2\dots A_n$。根据理论计算，机械臂的最佳性能参数为 $B_1, B_2\dots B_n$。为了提高机械臂的性能，拿到更高的分数，Jimmy 决定调整机械参数。

由于机械臂各个部件间具有关联性，修改某个参数的同时也会影响到另一个参数。具体来说，只有 m 种调整可以进行：给定 $(x_i, y_i)$，让 $A_{x_i} \gets A_{x_i} + p, A_{y_i} \gets A_{y_i} + p$，其中 $p$ 为任意整数，且调整次数不限。Jimmy 希望通过调整使得 $S =\sum \limits_{i=1}^n(A_i - B_i)^2$ 最小，请你帮他算出调整后 $S$ 的最小值。

输入格式

第一行两个整数 $n, m$，分别表示机械臂参数的个数，以及调整操作的种类数。

第二行 $n$ 个整数 $A_i$，表示机械臂当前的参数值。

第三行 $n$ 个整数 $B_i$，表示机械臂理论最佳的参数值。

接下来 $m$ 行每行两个整数 $x_i, y_i$，表示每种调整操作的两个目标参数。

输出格式

一行一个整数表示答案。

6 3
14 9 1 0 4 7
11 11 5 8 7 3
1 2
3 4
5 6

46

提示

数据范围

• 对于 $20\%$ 的数据，$1 \leq n, m \leq 5$，$0 \leq A_i, B_i \leq 5$。
• 另有 $40\%$ 的数据，所有 $B_i = 0$ 且所有 $x_i = 1$ 。
• 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq A_i, B_i \leq 10^5$。

注意：$(x_i, y_i)$ 可能出现重复。