<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

485. Arrays
Time limit per test: 1.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



You are given a sequence of 3· N integers (X1, X2, ·s, X3· N). Create three sequences (A1, A2, ·s, AN), (B1, B2, ·s, BN) and (C1, C2, ·s, CN) such that:


each of the integers from 1 to 3· N belongs to exactly one of the sequences A, B or C;

and the value of:

SUM from i=1 to N (Ai - Bi) * Ci

is the largest possible.


Input

Constraints on N	Constraints on T
1 ≤ N ≤ 10	1 ≤ T ≤ 1000
11 ≤ N ≤ 15	1 ≤ T ≤ 100
16 ≤ N ≤ 20	1 ≤ T ≤ 10
21 ≤ N ≤ 25	T = 1

The input file contains T test cases, all having the same value of N. The first line of the input file contains the integers T and N, constrained as shown in the adjacent table. Each of the following T lines describes one test case and contains 3· N integers, the members of the sequence X. All these values are in the range from 0 to 1000.

Output
The output file should consist of T lines. Each line should contain the largest possible value of S for the corresponding test case from the input file.

Example(s)
sample input
sample output
1 2
4 1 8 2 0 5
46



Note. The maximal value is attained by taking A = (1, 3), B = (2, 5), C = (4, 6).

<|response|>
1. Abridged Problem Statement
You have 3·N integers. You must partition them into three groups A, B, C of size N each (using each integer exactly once) and then reorder each group arbitrarily to maximize
   S = Σ_{i=1..N} (A_i – B_i) * C_i.
Given T test cases (all with the same N), compute the maximum S for each.

2. Key Observations
- Because B appears with a minus sign in every term, it is always optimal to assign the N smallest input values to B.
- After removing B, we are left with 2N values (call them AC). We must choose N of them to be A and N to be C. Once chosen, we sort A ascending and C ascending and pair index-for-index.
- Brute forcing which N out of 2N go to A (and the rest to C) costs O(C(2N,N)) which is too large for N up to 25.
- We can do a DP over bitmasks of size N by "scanning" the sorted AC array from largest to smallest, maintaining which of N "C-slots" are already filled. Each DP state is a mask of length N; bit=1 means that C-slot is occupied. As we move from one AC element to the next, we "shift" the window of slots, recycle one slot for A, and try placing the current AC element in any free C-slot below the first occupied bit.
- This rolling-mask DP has 2^N states and O(N) transitions each, for overall O(N·2^N) time, which fits N≤25.

3. Full Solution Approach
1. Read T and N.
2. For each test case:
   a. Read the 3N integers into an array X and sort X ascending.
   b. Let B = X[0..N–1] (the N smallest values).
   c. Let AC = X[N..3N–1], sorted ascending, of length 2N.
3. We will process AC from its largest element down to its smallest (i.e., from index 2N–1 down to 0). Define a DP array dp[mask] for mask in [0..2^N–1], initialized to 0. Here mask's 1-bits mark which of the N C-slots are already taken.
4. Precompute popcount(mask) for all masks. This tells how many C's have been chosen so far (call that cnt). We will pair the cnt-th smallest B with the next A–C pair we form.
5. We also maintain an integer top_zero, initially = N, which identifies the bit position of the newly recycled A-slot each step.
6. For each mask in [0..2^N–1]:
   a. cnt = popcount(mask).
   b. Compute next_mask = (mask << 1); if the bit at top_zero is set in next_mask, decrement top_zero.
   c. Set next_mask |= (1 << top_zero); truncate to N bits.
   d. For each i from 0..N–1 where (next_mask >> i) & 1 == 0 (break at the first 1-bit):
        newmask = next_mask | (1<<i)
        A_val = AC[n - cnt + top_zero - 1]
        B_val = B[cnt]
        C_val = AC[n - cnt + i - 1]
        gain = (A_val – B_val) * C_val
        dp[newmask] = max(dp[newmask], dp[mask] + gain)
7. The answer for this test is dp[(1<<N)–1], i.e. all C-slots filled.

Time complexity per test: O(N · 2^N). For N up to 25 this runs in about 1–1.5s in optimized C++.

4. C++ Implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> vals;

void read() {
    vals.resize(3 * n);
    cin >> vals;
}

int dp[1 << 25];
int8_t popcnt[1 << 25];

void precompute() {
    popcnt[0] = 0;
    for(int mask = 1; mask < (1 << 25); mask++) {
        popcnt[mask] = popcnt[mask >> 1] + (mask & 1);
    }
}

void solve() {
    // Sort the 3N values. It is always optimal to assign the smallest N values
    // to B, leaving the upper 2N values (call them AC) to be split between A
    // and C. We process A/C with a sliding-window bitmask DP: the mask records
    // which of the most recent AC positions have been chosen as C, and popcnt
    // of the mask is how many A/C pairs have been placed. For each mask we form
    // next_mask by shifting left (advancing the window) and inserting the next
    // A at the topmost free position; top_zero tracks that position. Each free
    // bit i in next_mask is a candidate slot for the matching C, and the
    // contribution of pairing the cnt-th largest A with that C, against the
    // cnt-th smallest B, is (A - B) * C. Shifting the window keeps each C close
    // to its A, which is what reduces the naive O*(4^n) to O*(2^n).

    vector<pair<int, int>> v;
    for(int i = 0; i < 3 * n; i++) {
        v.emplace_back(vals[i], i);
    }

    sort(v.begin(), v.end());

    vector<pair<int, int>> B, AC;
    B.insert(B.end(), v.begin(), v.begin() + n);
    AC.insert(AC.end(), v.begin() + n, v.end());

    memset(dp, 0, (1 << n) * sizeof(int));
    int top_zero = n;
    for(int mask = 0; mask < (1 << n); mask++) {
        int cnt = popcnt[mask];
        int next_mask = mask << 1;
        if((next_mask >> top_zero) & 1) {
            top_zero--;
        }

        next_mask |= (1 << top_zero);
        next_mask &= (1 << n) - 1;

        for(int i = 0; i < n; i++) {
            if((next_mask >> i) & 1) {
                break;
            }

            int Bj = B[cnt].first;
            int Aj = AC[n - cnt + top_zero - 1].first;
            int Cj = AC[n - cnt + i - 1].first;

            dp[next_mask | (1 << i)] =
                max(dp[next_mask | (1 << i)], dp[mask] + (Aj - Bj) * Cj);
        }
    }

    cout << dp[(1 << n) - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    int T = 1;
    cin >> T >> n;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation

```python
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    T, n = map(int, input().split())
    FULL = (1 << n) - 1

    # Precompute popcounts for 0..2^n-1
    popcnt = [0] * (1<<n)
    for m in range(1, 1<<n):
        popcnt[m] = popcnt[m>>1] + (m & 1)

    for _ in range(T):
        X = list(map(int, input().split()))
        X.sort()
        # Select B = N smallest
        B = X[:n]
        # The remaining 2N values
        AC = X[n:]

        # dp[mask] = best sum so far with this mask of chosen C-slots
        dp = [0] * (1<<n)

        # 'top_zero' is the index of the fresh slot to recycle each step
        top_zero = n

        # Process masks in ascending order => implicitly from largest AC to smallest
        for mask in range(1<<n):
            cnt = popcnt[mask]       # how many Cs chosen so far
            # Shift window
            next_mask = (mask << 1) & FULL

            # If the bit we dropped was zero, update top_zero
            if ((mask >> (n-1)) & 1) == 0:
                top_zero -= 1
            # Mark the recycled slot as occupied (will be used by an A)
            next_mask |= (1 << top_zero)

            # Try putting the new AC element into any free C-slot
            for i in range(n):
                if (next_mask >> i) & 1:
                    continue
                # B[cnt] is the next B
                Bj = B[cnt]
                # A is from the recycled slot
                Aj = AC[n - cnt + top_zero - 1]
                # C is from slot i
                Cj = AC[n - cnt + i - 1]
                newmask = next_mask | (1 << i)
                gain = (Aj - Bj) * Cj
                if dp[mask] + gain > dp[newmask]:
                    dp[newmask] = dp[mask] + gain

        # answer in full mask
        print(dp[FULL])

if __name__ == "__main__":
    main()
```
