题目描述

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

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

输入

从文件min.in中读入数据。

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

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

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

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

输出

输出到文件min.out中。

一行一个整数表示答案。

样例数据

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

46

数据范围

对于$20$%的数据，$0<n,m\le5,0\le A_i,B_i\le5$。

另有$40$% 的数据，所有$B_i=0且所有x_i=1$。

对于$100$%的数据，$0<n\le2\times10^5,0<m\le5\times10^5,0\le A_i,B_i\le10^5$。

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