# A. Array Balancing | Educational Codeforces Round 126

A. Array Balancing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

1. Choose integer index $i$ ($1\le i\le n$);
2. Swap ${a}_{i}$ and ${b}_{i}$.

What is the minimum possible sum $|{a}_{1}-{a}_{2}|+|{a}_{2}-{a}_{3}|+\cdots +|{a}_{n-1}-{a}_{n}|$ $+$ $|{b}_{1}-{b}_{2}|+|{b}_{2}-{b}_{3}|+\cdots +|{b}_{n-1}-{b}_{n}|$ (in other words, $\sum _{i=1}^{n-1}\left(|{a}_{i}-{a}_{i+1}|+|{b}_{i}-{b}_{i+1}|\right)$) you can achieve after performing several (possibly, zero) operations?

Input

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

The first line of each test case contains the single integer $n$ ($2\le n\le 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\le {a}_{i}\le {10}^{9}$) — the array $a$.

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

Output

For each test case, print one integer — the minimum possible sum $\sum _{i=1}^{n-1}\left(|{a}_{i}-{a}_{i+1}|+|{b}_{i}-{b}_{i+1}|\right)$.

Example
input
Copy
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

output
Copy
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=\left[3,3,3,3\right]$ and $b=\left[10,10,10,10\right]$ 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|+\cdots +|4-5|+|6-7|+\cdots +|9-10|$ $=4+4=8$.

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

${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;
}