First, if all numbers are equal, then there is no answer (since $$$a$$$ is divisible by $$$a$$$, if both arrays are non-empty, then $$$c_1$$$ is a divisor of $$$b_1$$$).

Second, if $$$a$$$ is divisible by $$$b$$$ and they are both natural numbers, then the following equality holds: $$$b \le a$$$ (by definition, if $$$a$$$ is divisible by $$$b$$$, then $$$a$$$ can be represented as $$$k \dot b$$$, where $$$k$$$ is a natural number).

Now we can place all instances of the smallest number into $$$b$$$, and all other numbers into $$$c$$$. It can be seen that such a construction always gives a valid answer.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
void solve() {
	int n = 0; cin >> n; 
	vector<int> inp; inp.assign(n, 0);
	for (auto& x : inp) cin >> x;
	sort(inp.begin(), inp.end());
	if (inp.back() == inp[0]) {
		cout << "-1\n";
		return;
	}
	else {
		int it = 0;
		while (inp[it] == inp[0]) it++;
		cout << it << " " << n - it << "\n";
		for (int j = 0; j < it; ++j) cout << inp[j] << " ";
		for (int j = it; j < n; ++j) cout << inp[j] << " ";
	}
}
 
int main() {
	int t = 0; cin >> t;
	while (t--) solve();
	return 0;
}

To increase the answer for each array separately, it is necessary to move the minimum to another array. Then, notice that it is optimal to move all the minimums to one array. Let's figure out which array. After moving the minimum from an array, the second minimum in the original array becomes the new minimum. Then, it is easy to notice that it is optimal to move all the minimums to the array with the smallest second minimum. After all the movements, we will have one array where the minimum element is the smallest number among all the arrays, and $$$n-1$$$ arrays where the minimum element is the second minimum in the original array.

Therefore, the answer to the problem will be $$$M + K - S$$$, where $$$M$$$ is the minimum element among all the arrays, $$$K$$$ is the sum of all the second minimums, and $$$S$$$ is the smallest second minimum.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
using namespace std;
 
#define all(v) v.begin(), v.end()
 
typedef long long ll;
 
const int INF = 1e9 + 7;
 
void solve() {
    int n;
    cin >> n;
 
    int minn = INF;
    vector<int> min2;
    for (int i = 0 ; i < n ; i++) {
        int m;
        cin >> m;
        vector<int> v(m);
        for (auto &el : v) cin >> el;
 
        int minel = *min_element(all(v));
        minn = min(minn, minel);
        v.erase(find(all(v), minel));
        min2.push_back(*min_element(all(v)));
    }
    cout << minn + (ll) accumulate(all(min2), 0ll) - *min_element(all(min2)) << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
#ifdef LOCAL
    freopen("a.in", "r", stdin);
#endif
 
    int t = 1;
    cin >> t;
    while (t--)
        solve();
 
    return 0;
}

Let's fix the maximum element in an array — let it be $$$M$$$. Now, let's iterate from $$$n$$$ to $$$1$$$. Let the current chosen number be $$$i$$$. I claim that if we maintain the remaining available numbers to multiply by, then it is optimal to take the maximum such number $$$x$$$ that $$$x * i \le M$$$.

Proof: let's say that this is not correct. Then, let's say that we pair $$$i$$$ with another number $$$x1$$$, and $$$x$$$ gets paired with some other number $$$i1$$$. Then, $$$i1 < i$$$, because it was chosen later, and $$$x1 < x$$$ (otherwise $$$i * x1 > M$$$). Now let's swap $$$x$$$ with $$$x1$$$. The sum is increased by $$$i * x - i * x1 - i1 * x + i1 * x1 = (i - i1)(x - x1) > 0$$$, and all of the numbers are less or equal to $$$M$$$.

Now the task can be solved in $$$O(N^3logN)$$$ by simply iterating on the maximum from $$$N^2$$$ to $$$1$$$, while maintaining the remaining numbers with a set. In order to squeeze it in the TL, you can only consider such maximums that they can be represented as $$$i * j, 1 \le i, j \le n$$$.

In order to optimize it to $$$O(N^3)$$$, let's notice that for each number $$$x$$$, it can be paired with any number from $$$1$$$ to $$$\frac{M} {x}$$$. Now just maintain a stack of all available elements at the current moment, add all numbers that possible, and pop the maximum number for all $$$i$$$ from $$$1$$$ to $$$N$$$.

#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
using namespace std;
void solve() {
	int N = 0; cin >> N;
	int ans = 0;
	vector<int> pr;
	pr.assign(N * N, -1);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			pr[i * j - 1] = 1;
		}
	}
	for (int mx = N * N; mx >= 1; --mx) {
		if (pr[mx - 1] == -1) continue;
		vector<vector<int>> a;
		int curans = -mx;
		bool br = false;
		a.assign(N, vector<int>());
		for (int j = N; j >= 1; --j) {
			int num = min(mx / j, N);
			if (num < 1) {
				br = true;
				break;
			}
			a[num - 1].push_back(j);
		}
		if (br) break;
		stack<int> s;
		for (int i = 0; i < N; ++i) {
			s.push(i + 1);
			bool brk = false;
			for (auto x : a[i]) {
				if (s.empty()) {
					brk = true; break;
				}
				curans += s.top() * x;
				s.pop();
			}
			if (brk) break;
		}
		ans = max(ans, curans);
	}
	cout << ans << "\n";
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 0; cin >> t;
	while (t--) solve();
	return 0;
}