B. Olya and Game with Arrays

Artem suggested a game to the girl Olya. There is a list of 𝑛 arrays, where the 𝑖 -th array contains 𝑚𝑖≥2 positive integers 𝑎𝑖,1,𝑎𝑖,2,…,𝑎𝑖,𝑚𝑖 . Olya can move at most one (possibly 0 ) integer from each array to another array. Note that integers can be moved from one array only once, but integers can be added to one array multiple times, and all the movements are done at the same time.

time limit per test: 1 second | memory limit per test: 256 megabytes

Artem suggested a game to the girl Olya. There is a list of n arrays, where the i-th array contains m_i ≥ 2 positive integers a_i,1, a_i,2, …, a_{i,m_i}.

Olya can move at most one (possibly 0) integer from each array to another array. Note that integers can be moved from one array only once, but integers can be added to one array multiple times, and all the movements are done at the same time.

The beauty of the list of arrays is defined as the sum ∑ⁿ_i=1 min^m_i_j=1 a_i,j. In other words, for each array, we find the minimum value in it and then sum up these values.

The goal of the game is to maximize the beauty of the list of arrays. Help Olya win this challenging game!

Input

Each test consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 25000) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 25000) — the number of arrays in the list.

This is followed by descriptions of the arrays. Each array description consists of two lines.

The first line contains a single integer m_i (2 ≤ m_i ≤ 50000) — the number of elements in the i-th array.

The next line contains m_i integers a_i,1, a_i,2, …, a_{i,m_i} (1 ≤ a_i,j ≤ 10⁹) — the elements of the i-th array.

It is guaranteed that the sum of m_i over all test cases does not exceed 50000.

Output

For each test case, output a single line containing a single integer — the maximum beauty of the list of arrays that Olya can achieve.

Example

Input

3
2
2
1 2
2
4 3
1
3
100 1 6
3
4
1001 7 1007 5
3
8 11 6
2
2 9

Output

5
1
19

Note

In the first test case, we can move the integer 3 from the second array to the first array. Then the beauty is min(1, 2, 3) + min(4) = 5. It can be shown that this is the maximum possible beauty.

In the second test case, there is only one array, so regardless of the movements, the beauty will be min(100, 1, 6) = 1.

void solve()
{

  int n;
  cin >> n;
  vector<vi> v;
  int mn = 1e10;
  int idx = 0;
  for (int i = 0; i < n; i++)
  {
    int k;
    cin >> k;
    vi temp(k);
    for (int j = 0; j < k; j++)
    {
      cin >> temp[j];
      if (mn > temp[j])
      {
        mn = temp[j];
        idx = i;
      }
    }
    v.pb(temp);
  }

  vpi ans;
  for (int i = 0; i < n; i++)
  {
    sort(v[i].begin(), v[i].end());
    ans.pb({v[i][1], i});
  }

  sort(ans.begin(), ans.end());
  int res = 0;
  for (int i = 1; i < ans.size(); i++)
    res += ans[i].first;

  for (int i = 0; i < n; i++)
  {
    mn = min(mn, v[i][0]);
  }

  cout << res + mn << endl;

  // 5 7
  //  6 8
  //  2 9
}


#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
#define scanit(a, n)                           \
  for (ll indexaa = 0; indexaa < n; indexaa++) \
    cin >> a[indexaa];

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;
  vector<vi> v;
  int mn = 1e10;
  int idx = 0;
  for (int i = 0; i < n; i++)
  {
    int k;
    cin >> k;
    vi temp(k);
    for (int j = 0; j < k; j++)
    {
      cin >> temp[j];
      if (mn > temp[j])
      {
        mn = temp[j];
        idx = i;
      }
    }
    v.pb(temp);
  }

  vpi ans;
  for (int i = 0; i < n; i++)
  {
    sort(v[i].begin(), v[i].end());
    ans.pb({v[i][1], i});
  }

  sort(ans.begin(), ans.end());
  int res = 0;
  for (int i = 1; i < ans.size(); i++)
    res += ans[i].first;

  for (int i = 0; i < n; i++)
  {
    mn = min(mn, v[i][0]);
  }

  cout << res + mn << endl;

  // 5 7
  //  6 8
  //  2 9
}

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

TagsB. Olya and Game with ArraysCodeforces Round 892 (Div. 2)Codeforces

Raunit Verma

Technical Writer at CodingKaro

Share this on