Optimizing Robotic Arm Performance

Jimmy has designed a robotic arm for his final project in the course Mechanical Design and Manufacturing. He measured its performance parameters \(A_1, A_2, \dots, A_n\) (such as dimensions, hardness, flexibility, maximum grip, etc.) and computed the optimal parameters \(B_1, B_2, \dots, B_n\) theoretically.

Due to the interdependency among the mechanical parts, adjusting one parameter will affect another. Specifically, there are exactly \(m\) types of adjustments available. In each adjustment, given a pair \((x_i, y_i)\), Jimmy can add an arbitrary integer \(p\) simultaneously to both \(A_{x_i}\) and \(A_{y_i}\):

\[ A_{x_i} \gets A_{x_i} + p, \quad A_{y_i} \gets A_{y_i} + p \]

He may perform each type of adjustment an unlimited number of times. Note that if a parameter is not involved in any adjustment pair, it cannot be modified.

The goal is to minimize

\[ S = \sum_{i=1}^{n} (A_i - B_i)^2 \]

Help Jimmy determine the minimum possible value of \(S\) after applying any number of allowed adjustments.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le 10^5\)).

The second line contains \(n\) integers representing the array \(A\): \(A_1, A_2, \dots, A_n\).

The third line contains \(n\) integers representing the array \(B\): \(B_1, B_2, \dots, B_n\).

Then \(m\) lines follow, each containing two integers \(x_i\) and \(y_i\) (1-indexed) which indicate that an adjustment can be made by adding the same integer \(p\) to both \(A_{x_i}\) and \(A_{y_i}\).

outputFormat

Output a single integer representing the minimum value of \(S = \sum_{i=1}^{n} (A_i - B_i)^2\) after optimally applying the allowed adjustments.

sample

3 1
1 2 3
2 2 2
1 2

2