### PROBLEM LINK:

**Author:** Aleksa Plavsic

**Tester:** Hussain Kara Fallah

**Editorialist:** Hussain Kara Fallah

### PROBLEM

You are given two integer sequences **S _{1}, S_{2}, S_{3}…S_{N}**, and

**T**and an integer

_{1}, T_{2}, T_{3}…T_{M}**X**.

You are allowed to perform the following operation any number of times:

Choose an element of **S** and an element of **T** (let’s denote them by **S _{i}** and

**T**respectively), then decrease both

_{j}**S**and

_{i}**T**by

_{j}**X**, i.e. replace

**S**by

_{i}**S**and

_{i}-X**T**.

_{j}-XLet’s denote the minimum and maximum value in the sequence **S** after performing the chosen operations (possibly none) by **minS** and **maxS** respectively. Similarly, let’s denote the minimum and maximum value in **T** after performing the chosen operations by **minT** and **maxT** respectively. The goal is minimizing the expression **(maxS+maxT)−(minS+minT)**. Compute the minimum value of this expression.

PREREQUISTES:

Basic Number Theory

### CONSTRAINTS

**N,M <= 5*10 ^{5}**

**All other values don’t exceed 10 ^{9}**.

### DIFFICULTY

Medium

### EXPLANATION

A very important observation:

The answer is always no more than **2*X**. Let’s try first to make all the values of one array in the range **[0,X-1]**.

Let’s introduce:

sum_1 = \sum_{i = 1}^{N} \lfloor \frac{A_i}{X} \rfloor

sum_2 = \sum_{i = 1}^{M} \lfloor \frac{A_i}{X} \rfloor

For simplicity let’s assume that sum2 > sum1. We need to apply this operation **sum1** times to the first array to make all values in the range **[0…X-1]**. Since **sum2 > sum1** then we can pick **sum1** pairs from both arrays and apply the operation.

The second array won’t be in the range **[0…X-1]** necessarily. We need to apply a few more **sum2-sum1** operations to transform all numbers into that interval. Actually, we can do that, by picking each time a number from the second array with the maximum number in the first array (doing this operation **sum2 - sum1** times). You can see that the difference between the maximum number and the minimum in the first won’t ever exceed **X** (Try to prove it, it’s easy).

Now we have the first array with **maximum - minimum <= X** and the second array has all numbers in the range **[0…X-1]**.

By observing the problem a little bit, we can see that the optimal solution is to apply the same operation N*M times always by picking the maximum number in the first array and the maximum number in the second array. This will be enough to solve 2 subtasks. (because it’s the only way to keep the difference in each array no more than **X**) and we can prove that there is no optimal scenario where the difference between the max and the min in one of the arrays is more than **X**. It’s also obvious that N*M operations are enough because it’s the number of all rotations of first multiplied by the number of all rotations of the second.

If **GCD(N,M) = 1**, we can prove that for any pair of indices (the first index is from the first array and the second index from the second array), we can prove that we can fix them as the starting elements of our arrays by applying this operation a finite number of times **(because GCD(N,M)=1)**. (Try the proof yourself).

Then the answer can be calculated easily. Let’s take the difference between every 2 consecutive elements in both arrays (take into account that last and first element are equal), our answer would be the sum of the minimum difference in the first + the minimum difference in the second.

If **GCD(N,M)!=1** . We must group our numbers by their modulo to **G (by G we mean GCD(N,M))**. It would be possible also to fix any pair of elements ( ** S_{i}, T_{j} ** each of them to be the starting number of its corresponding array) if and only if **i Modulo G = j Modulo G**.

As a conclusion, we take the differences between every 2 consecutive elements in both arrays, group them by modulo. For each group take the minimum possible difference. Check each modulo, and calculate the sum of the best differences (in both arrays). Our answer would be the minimum cost of all modulos.

### Complexity

**O(n log n + m log m)** for sorting.

Rest of calculations can be done in **O(n + m)**

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s/Editorialist’s solution can be found here.