A. Array Balancing | Educational Codeforces Round 126

You are given two arrays of length $n$ : $a_{1}, a_{2}, \dots, a_{n}$ and $b_{1}, b_{2}, \dots, b_{n}$ .

You can perform the following operation any number of times:

Choose integer index $i$ ( $1 \leq i \leq n$ );
Swap $a_{i}$ and $b_{i}$ .

What is the minimum possible sum $| a_{1} - a_{2} | + | a_{2} - a_{3} | + \dots + | a_{n - 1} - a_{n} |$ $+$ $| b_{1} - b_{2} | + | b_{2} - b_{3} | + \dots + | b_{n - 1} - b_{n} |$ (in other words, $\sum_{i = 1}^{n - 1} (| a_{i} - a_{i + 1} | + | b_{i} - b_{i + 1} |)$ ) you can achieve after performing several (possibly, zero) operations?

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 4000$ ) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains the single integer $n$ ( $2 \leq n \leq 25$ ) — the length of arrays $a$ and $b$ .

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ) — the array $a$ .

The third line of each test case contains $n$ integers $b_{1}, b_{2}, \dots, b_{n}$ ( $1 \leq b_{i} \leq 10^{9}$ ) — the array $b$ .

Output

For each test case, print one integer — the minimum possible sum $\sum_{i = 1}^{n - 1} (| a_{i} - a_{i + 1} | + | b_{i} - b_{i + 1} |)$ .

Example
inputCopy
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100
outputCopy
0
8
218

Note

In the first test case, we can, for example, swap $a_{3}$ with $b_{3}$ and $a_{4}$ with $b_{4}$ . We'll get arrays $a = [3, 3, 3, 3]$ and $b = [10, 10, 10, 10]$ with sum $3 \cdot | 3 - 3 | + 3 \cdot | 10 - 10 | = 0$ .

In the second test case, arrays already have minimum sum (described above) equal to $| 1 - 2 | + \dots + | 4 - 5 | + | 6 - 7 | + \dots + | 9 - 10 |$ $= 4 + 4 = 8$ .

In the third test case, we can, for example, swap $a_{5}$ and $b_{5}$

$b_{5}$ .

The solution to the above question is

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {

int n;
cin>>n;

vi a(n,0),b(n,0);
for (int i = 0; i < n; i++)
{
    cin>>a[i];
}

for (int i = 0; i < n; i++)
{
    cin>>b[i];
}
int ans=0;
int noswap=0;

for (int i = 0; i < n-1; i++)
{   

    int curr=abs(a[i+1]-a[i])+abs(b[i+1]-b[i]);
    int curr2=abs(a[i+1]-b[i])+abs(a[i]-b[i+1]);
    if(curr2>curr){
        swap(a[i],b[i]);
    }
    ans+=min(curr,curr2);
}
cout<<ans<<endl;





}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
  cin >> t;
  while (t--) solve();



  return 0;
}