[Solution] Fault-tolerant Network solution codeforces

Fault-tolerant Network solution codeforces – There is a classroom with two rows of computers. There are 𝑛n computers in each row and each computer has its own grade. Computers in the first row has grades 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an and in the second row — 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn.

Initially, all pairs of neighboring computers in each row are connected by wire (pairs (𝑖,𝑖+1)(i,i+1) for all 1𝑖<𝑛1≤i<n), so two rows form two independent computer networks.

Fault-tolerant Network solution codeforces

Your task is to combine them in one common network by connecting one or more pairs of computers from different rows. Connecting the 𝑖i-th computer from the first row and the 𝑗j-th computer from the second row costs |𝑎𝑖𝑏𝑗||ai−bj|.

You can connect one computer to several other computers, but you need to provide at least a basic fault tolerance: you need to connect computers in such a way that the network stays connected, despite one of its computer failing. In other words, if one computer is broken (no matter which one), the network won’t split in two or more parts.

That is the minimum total cost to make a fault-tolerant network?

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. Next 𝑡t cases follow.

The first line of each test case contains the single integer 𝑛n (3𝑛21053≤n≤2⋅105) — the number of computers in each row.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the grades of computers in the first row.

The third line contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖1091≤bi≤109) — the grades of computers in the second row.

It’s guaranteed that the total sum of 𝑛n doesn’t exceed 21052⋅105.

Fault-tolerant Network solution codeforces

For each test case, print a single integer — the minimum total cost to make a fault-tolerant network.

Example
input

Copy
2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000
output

Copy
31
1999999998

Fault-tolerant Network solution codeforces

In the first test case, it’s optimal to connect four pairs of computers:

  1. computer 11 from the first row with computer 22 from the second row: cost |14|=3|1−4|=3;
  2. computer 33 from the first row with computer 22 from the second row: cost |14|=3|1−4|=3;
  3. computer 22 from the first row with computer 11 from the second row: cost |1020|=10|10−20|=10;
  4. computer 22 from the first row with computer 33 from the second row: cost |1025|=15|10−25|=15;

In total, 3+3+10+15=313+3+10+15=31.In the second test case, it’s optimal to connect 11 from the first row with 11 from the second row, and 44 from the first row with 44 from the second row.

 

Leave a Comment