eolymp
bolt
Try our new interface for solving problems
Problems

Fast Squarier Transform

Fast Squarier Transform

Time limit 2 seconds
Memory limit 256 MiB

You are given two arrays of integers [a_1, a_2, \dots, a_n] and [b_1, b_2, \dots, b_m].

Find the following value:

\sum_{i = 1}^n\sum_{j = 1}^m \lfloor \sqrt{|a_i - b_j|} \rfloor.

Note that \lfloor x \rfloor denotes the maximum integer not exceeding x, and |x| denotes the absolute value of x.

Input data

The first line of the input contains 2 integers n, m (1 \leq n, m \leq 10^5).

The second line of the input contains n integers a_1, a_2, \dots, a_n (0 \le a_i, a_1 + a_2 + \ldots + a_n \le 2\cdot 10^7).

The third line of the input contains m integers b_1, b_2, \dots, b_m (0 \le b_i, b_1 + b_2 + \ldots + b_m \le 2\cdot 10^7).

Output data

Print a single integer — the sum from the statement.

Examples

Input example #1
1 2
1
2 3
Output example #1
2
Input example #2
2 3
1 2
3 4 5
Output example #2
7

Note

In the first sample the answer is \lfloor \sqrt{|1 - 2|} \rfloor + \lfloor \sqrt{|1 - 3|} \rfloor = \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor = 1 + 1 = 2.

In the second sample, the answer is \lfloor \sqrt{|1 - 3|} \rfloor + \lfloor \sqrt{|1 - 4|} \rfloor + \lfloor \sqrt{|1 - 5|} \rfloor + \lfloor \sqrt{|2 - 3|} \rfloor + \lfloor \sqrt{|2 - 4|} \rfloor + \lfloor \sqrt{|2 - 5|} \rfloor = \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 1 + 1 + 2 + 1 + 1 + 1 = 7.

Author Anton Trygub
Source All-Ukrainian Collegiate Programming Contest 2021-2022, II stage