#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;


#undef assert
#define assert(x)
#define cerr if(0)cerr

const int WRITE = 1, READ = 2, ADD = 3;

struct Ope {
	int type;
	ll value = 0;
	void read() {
		char c;
		scanf(" %c", &c);
		if(c == 'Z') {
			type = WRITE;
		}
		else if(c == 'W') {
			type = READ;
		}
		else if(c == '+') {
			type = ADD;
			scanf("%lld", &value);
		}
		else if(c == '-') {
			type = ADD;
			scanf("%lld", &value);
			value *= -1;
		}
		else {
			assert(false); // unknown operation
		}
	}
};
debug & operator << (debug & dd, Ope p) {
	if(p.type == WRITE) dd << (p.value >= 0 ? "+" : "") << p.value << " W ";//"W ";
	else if(p.type == READ) dd << "R ";
	// else if(p.type == ADD) dd << (p.value > 0 ? "+" : "") << p.value << " ";
	else assert(false);
	return dd;
}

struct Block {
	ll just, total;
};
debug & operator << (debug & dd, Block p) {
	dd << make_pair(p.just, p.total);
	return dd;
}

struct Row {
	int id;
	vector<Block> blocks;
	bool first_write = false;
	ll value = 0;
	bool empty() const {
		return blocks.empty();
	}
	void skip() {
		assert(!blocks.empty());
		blocks.pop_back();
	}
	void make_operation(ll& global) {
		assert(!blocks.empty());
		global += blocks.back().total;
		blocks.pop_back();
	}
};
debug & operator << (debug & dd, Row p) {
	dd << "my=" << p.value << " ";
	vector<Block> tmp = p.blocks;
	reverse(tmp.begin(), tmp.end());
	for(Block block : tmp) {
		dd << block;
	}
	return dd;
}

struct OldRow {
	ll value;
	vector<Ope> operations;
	bool empty() const {
		return operations.empty();
	}
	Row read() {
		value = 0;
		int cnt;
		scanf("%d", &cnt);
		while(cnt--) {
			Ope nowe;
			nowe.read();
			while(!operations.empty()) {
				Ope old = operations.back();
				if(old.type == WRITE && nowe.type == WRITE) {
					// avoid three in a row
					if((int) operations.size() >= 2 && operations.end()[-2].type == WRITE) {
						nowe.value += old.value;
						operations.pop_back();
					}
					else if(nowe.value <= 0) { // || nowe.value <= old.value) {
						nowe.value += old.value;
						operations.pop_back();
					}
					else {
						break;
					}
				}
				else if(old.type == nowe.type) {
					if(nowe.type == ADD) {
						nowe.value += old.value;
					}
					operations.pop_back();
				}
				else if(nowe.type == READ && old.type == ADD) {
					operations.pop_back();
				}
				else if(nowe.type == WRITE && old.type == ADD) {
					nowe.value += old.value;
					operations.pop_back();
				}
				else {
					break;
				}
			}
			operations.push_back(nowe);
		}
		while(!operations.empty() && operations.back().type != WRITE) {
			operations.pop_back();
		}
		if((int) operations.size() >= 2 && operations[0].type == ADD && operations[1].type == READ) {
			operations.erase(operations.begin());
		}
		// last is WRITE
		debug dd;
		dd << operations.size() << "   ";
		for(Ope ope : operations) {
			dd << ope;
		}
		
		// checks
		Row row;
		
		if(!operations.empty()) {
			int n = operations.size();
			int nxt = 0;
			int type = operations[0].type;
			assert(type == READ || type == WRITE);
			if(type == WRITE) {
				row.first_write = true;
			}
			while(nxt < n) {
				assert(operations[nxt].type == type);
				if(type == READ) {
					nxt++;
					type = WRITE;
				}
				else {
					assert(type == WRITE);
					nxt++;
					if(nxt < n && operations[nxt].type == WRITE) {
						assert(operations[nxt].value > 0);
						ll prv = operations[nxt-1].value;
						ll me = operations[nxt].value;
						row.blocks.push_back(Block{prv, prv + me});
						nxt++;
					}
					else {
						ll prv = operations[nxt-1].value;
						row.blocks.push_back(Block{prv, prv});
					}
					type = READ;
				}
			}
			assert(type == READ); // last was WRITE
		}
		reverse(row.blocks.begin(), row.blocks.end());
		
		return row;
		
		// reverse(operations.begin(), operations.end());
	}
	void make_operation(ll& global) {
		assert(!empty());
		Ope ope = operations.back();
		if(ope.type == READ) {
			value = global;
		}
		else if(ope.type == WRITE) {
			value += ope.value;
			global = value;
		}
		// else if(ope.type == ADD) {
			// value += ope.value;
		// }
		else {
			assert(false);
		}
		operations.pop_back();
	}
	void skip() {
		assert(!empty());
		operations.pop_back();
	}
};

void min_self(ll& a, ll b) {
	a = min(a, b);
}
const long long INF = LONG_LONG_MAX / 3;

/*
const int nax = 505;
long long dp[nax][nax][2]; // (i, eaten_intervals, was eating)
*/
struct Info {
	int first, second;
	long long value;
};

Info get_interval(const Row& row, bool is_start, bool is_end) {
	int small = 0;
	bool continuation = false;
	for(int i = 0; i < (int) row.blocks.size(); ++i) {
		int j = (int) row.blocks.size() - 1 - i;
		if(continuation && row.blocks[j].just == 0 && row.blocks[j].total == 0) {
			continue;
		}
		if(j == 0 && is_end) {
			if(!continuation) {
				small++;
			}
			continue;
		}
		if(row.blocks[j].just < 0 || (i == 0 && is_start)) {
			if(!continuation) {
				small++;
			}
			if(row.blocks[j].total == row.blocks[j].just) {
				// biore caly
				continuation = true;
			}
			else {
				continuation = false;
			}
		}
		else {
			continuation = false;
		}
		// debug() << imie(i) imie(continuation);	
	}
	if(is_start && is_end) {
		small = max(small, 2);
	}
	// debug() << imie(row) imie(small) imie(correct) imie(is_start) imie(is_end);
	// assert(small == correct.first);
	int big = 0;
	long long value = 0;
	for(int i = 0; i < (int) row.blocks.size(); ++i) {
		if(row.blocks[i].just <= 0 || (i == 0 && is_end) || (i == (int) row.blocks.size() - 1 && is_start)) {
			if(i == 0 && is_end) {
				value += row.blocks[i].total;
			}
			else {
				value += row.blocks[i].just;
			}
			big++;
		}
	}
	// debug() << imie(row) imie(big) imie(correct);
	
	// assert(big == correct.second);
	
	// debug() << imie(row) imie(value) imie(correct_value) imie(is_start) imie(is_end);
	// assert(value == correct_value);
	
	return Info{small, big, value};
}

void mini(pair<long long, int>& a, const pair<long long, int>& b) {
	a = min(a, b);
}
Info aliens(const Row& row, long long penalty, bool is_start, bool is_end) {
	
	cerr << "X";
	int n = row.blocks.size();
	// reverse(row.blocks.begin(), row.blocks.end());
	// reverse(row.blocks.begin(), row.blocks.end());
	// reverse(row.blocks.begin(), row.blocks.end());
	
	vector<pair<long long, int>> both;
	// debug() << imie(row.blocks[0].total);
	for(int rep : {-1, 1}) {
		auto add = [&](const pair<long long, int>& p, const long long& value, const int& cnt) {
			return make_pair(p.first + value + cnt * penalty, p.second + cnt * rep);
		};
		
		if(is_start && is_end) {
			// cerr << "x";
			pair<long long, int> skipped[2], eating[2];
			skipped[0] = make_pair(0LL, 0);
			eating[0] = skipped[1] = eating[1] = make_pair(INF, 0);
			for(int i = 0; i < n; ++i) {
				const Block& block = row.blocks[n-1-i];
				pair<long long, int> new_skip[2], new_eat[2];
				new_skip[0] = new_skip[1] = new_eat[0] = new_eat[1] = make_pair(INF, 0);
				for(int z = 0; z < 2; ++z) {
					if(skipped[z].first < INF) {
						if(i > 0 || !is_start) {
							mini(new_skip[z], skipped[z]);
						}
						mini(new_eat[z], add(skipped[z], block.total, 1));
						mini(new_skip[1], add(skipped[z], block.just, 1));
					}
					if(eating[z].first < INF) {
						mini(new_skip[1], eating[z]);
						mini(new_eat[z], add(eating[z], block.total, 0));
						mini(new_skip[1], add(eating[z], block.just, 0));
					}
				}
				for(int z = 0; z < 2; ++z) {
					skipped[z] = new_skip[z];
					eating[z] = new_eat[z];
				}
				// skipped = new_skip;
				// eating = new_eat;
			}
		
			pair<long long, int> answer = eating[1];
			if(!is_end) {
				mini(answer, skipped[1]);
			}
			debug() << imie(answer);
			answer.second = abs(answer.second);
			// answer.first -= answer.second * penalty;
			both.push_back(answer);
			continue;
		}
		
		pair<long long, int> skipped, eating;
		skipped = make_pair(0LL, 0);
		eating = make_pair(INF, 0);
		for(int i = 0; i < n; ++i) {
			const Block& block = row.blocks[n-1-i];
			pair<long long, int> new_skip, new_eat;
			new_skip = new_eat = make_pair(INF, 0);
			if(skipped.first < INF) {
				if(i > 0 || !is_start) {
					mini(new_skip, skipped);
				}
				mini(new_eat, add(skipped, block.total, 1));
				mini(new_skip, add(skipped, block.just, 1));
			}
			if(eating.first < INF) {
				mini(new_skip, eating);
				mini(new_eat, add(eating, block.total, 0));
				mini(new_skip, add(eating, block.just, 0));
			}
			
			skipped = new_skip;
			eating = new_eat;
		}
	
		pair<long long, int> answer = eating;
		if(!is_end) {
			mini(answer, skipped);
		}
		debug() << imie(answer);
		answer.second = abs(answer.second);
		// answer.first -= answer.second * penalty;
		both.push_back(answer);
	}
	debug() << imie(row) imie(penalty) imie(both);
	assert(both[0].first == both[1].first);
	assert(both[0].second >= both[1].second);
	
	return Info{both[1].second, both[0].second, both[0].first};
	// return answer;
}

/*
vector<long long> _run_dp(Row row, bool is_start, bool is_end) {
	int n = row.blocks.size();
	reverse(row.blocks.begin(), row.blocks.end());
	// 0 - was skipped
	// 1 - was eating
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= n; ++j) {
			for(int type : {0, 1}) {
				dp[i][j][type] = INF;
			}
		}
	}
	dp[0][0][0] = 0LL;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j <= i; ++j) {
			long long me = dp[i][j][0];
			if(me != INF) {
				if(i > 0 || !is_start) {
					min_self(dp[i+1][j][0], me); // keep skipping
				}
				min_self(dp[i+1][j+1][1], me + row.blocks[i].total); // start and keep eating
				min_self(dp[i+1][j+1][0], me + row.blocks[i].just); // start (eat first) and immediately stop eating
			}
			me = dp[i][j][1];
			if(me != INF) {
				min_self(dp[i+1][j][0], me); // skip this time
				min_self(dp[i+1][j][1], me + row.blocks[i].total); // keep eating
				min_self(dp[i+1][j][0], me + row.blocks[i].just); // eat first, then stop
			}
		}
	}
	vector<long long> ret(n + 1, INF);
	for(int j = 0; j <= n; ++j) {
		ret[j] = dp[n][j][1];
		if(!is_end) {
			min_self(ret[j], dp[n][j][0]);
		}
	}
	if(is_start && is_end) {
		ret[1] = INF;
	}
	// debug() << imie(row) imie(is_start) imie(is_end) imie(ret);
	// int first = 0;
	// while(first < (int) ret.size() && ret[first] == INF) {
		// first++;
	// }
	// if(is_start && is_end) {
		// assert(first == 2);
	// }
	// else if(is_start || is_end) {
		// assert(first == 1);
	// }
	// else {
		// assert(first == 0);
	// }
	// for(int i = first; i < (int) ret.size(); ++i) {
		// assert(ret[i] != INF);
	// }
	// vector<long long> diff;
	// for(int i = first; i + 1 < (int) ret.size(); ++i) {
		// diff.push_back(ret[i+1] - ret[i]); // -INF
	// }
	// debug();
	// debug() << imie(row) imie(is_start) imie(is_end);
	// debug() << imie(ret);
	// debug() << imie(diff);
	// for(int i = 0; i < (int) diff.size() - 1; ++i) {
		// assert(diff[i] <= diff[i+1]);
	// }
	return ret;
}*/

pair<int,int> get_min(const vector<long long>& row) {
	// for sure not all INF
	int n = row.size();
	int L = 0;
	while(L + 1 < n && (row[L] >= INF || row[L] > row[L+1])) {
		L++;
	}
	int R = L;
	while(R + 1 < n && row[R] == row[R+1]) {
		R++;
	}
	return {L, R};
}

set<int> s_cand;
vector<int> v_cand;
long long solve(const vector<Row>& all, int start, int end) {
	int n = all.size();
	
	vector<Info> they(n);
	pair<int,int> sum_interval{0, 0};
	for(int i = 0; i < n; ++i) {
		they[i] = get_interval(all[i], start == i, end == i);
		sum_interval.first += they[i].first;
		sum_interval.second += they[i].second;
	}
	
	int boss = -1;
	long long cool_answer = 0;
	for(int i = 0; i < n; ++i) {
		const Info& me = they[i];
		cool_answer += me.value;
		int special = 2 * me.first + (start != i) + (end != i) - 1;
		int sum_all = sum_interval.second - (me.second - me.first);
		assert(end != -1);
		if(special > sum_all) {
			boss = i;
			if(!s_cand.count(all[i].id)) {
				s_cand.insert(all[i].id);
				v_cand.push_back(all[i].id);
			}
			// if(find(candidates.begin(), candidates.end(), all[i].id) == candidates.end()) {
				// candidates.push_back(all[i].id);
			// }
		}
	}
	
	debug() << imie(cool_answer) imie(start) imie(end);
	
	if(boss == -1) {
		return cool_answer;
	}
	
	debug() << imie(boss);
	
	cool_answer -= they[boss].value;
	
	vector<long long> diff; // actually, this is heur
	for(int i = 0; i < n; ++i) {
		if(i != boss) {
			Row row = all[i];
			for(int j = (i == end); j < (int) row.blocks.size() - (i == start); ++j) {
				if(row.blocks[j].just > 0) {
					diff.push_back(row.blocks[j].just);
				}
			}
		}
	}
	// heur.push_back(0);
	diff.push_back(0); // fake element
	// sort(heur.begin(), heur.end());
	sort(diff.begin(), diff.end());
	// assert(heur == diff);
	assert(diff[0] >= 0);
	for(int i = 1; i < (int) diff.size(); ++i) {
		diff[i] += diff[i-1];
	}
	// int perfect = intervals[boss].first;
	int sum_others = sum_interval.second - they[boss].second;
	// jem[boss] - 1 + (end != boss) + (start != boss) <= sum_others
	
	
	if(true) { //if(boss == start && boss == end) { //boss != start || boss != end) {
		long long heur = INF;
		long long low = 0, high = 2e15L + 5;
		int turn = 0;
		while(low <= high) {
			long long penalty = (low + high) / 2;
			if(++turn <= 3) {
				penalty = llround(sqrt((long double) low * high));
			}
		// for(long long penalty = 0; penalty <= 100; ++penalty) {
			Info info = aliens(all[boss], penalty, boss == start, boss == end);
			debug() << ">> " imie(penalty) imie(info.first) imie(info.second) imie(all[boss].blocks.size()) imie(boss) imie(start) imie(end);
			bool too_big = false;
			for(int i = info.first; i <= info.second; ++i) {
				int j = max(0, i - 1 + (end != boss) + (start != boss) - sum_others);
				if(j < (int) diff.size()) {
					if(info.value < INF / 2) min_self(heur, info.value - i * penalty + diff[j] + cool_answer);
					if((j ? diff[j]-diff[j-1] : 0LL) > penalty) {
						too_big = true;
					}
				}
				else {
					too_big = true;
				}
				// for(int j = 0; j < (int) diff.size(); ++j) {
					// if(i - 1 + (end != boss) + (start != boss) <= sum_others + j) {
						// min_self(heur, info.value - i * penalty + diff[j] + cool_answer);
					// }
				// }
			}
			if(!too_big) {
				high = penalty - 1;
			}
			else {
				low = penalty + 1;
			}
		}
		return heur;
	}
	/*
	
	
	vector<long long> me = _run_dp(all[boss], boss == start, boss == end);
	
	// const vector<long long>& me = values[boss];
	// debug();
	debug() << "BOSS-case " imie(diff) imie(me);
	long long answer = INF;
	for(int i = 0; i < (int) me.size(); ++i) {
		// if(i - 1 + (end != boss) + (start != boss) <= sum_others + j) {
		int j = max(0, i - 1 + (end != boss) + (start != boss) - sum_others);
		if(j < (int) diff.size()) {
			if(me[i] != INF) {
				min_self(answer, me[i] + diff[j] + cool_answer);
			}
		}
	}
	return answer;*/
	
	
	
	
	/*
	if(true || (boss != start || boss != end)) {
		// ...
		debug() << imie(all[boss]);
		debug() << imie(heur) imie(answer);
		// assert(heur == answer);
		return heur;*/
		
		/*for(int j = 0; j < (int) diff.size(); ++j) {
			long long penalty = 0;
			if(j > 0) {
				penalty = diff[j] - diff[j-1];
			}
			Info info = aliens(all[boss], penalty, boss == start, boss == end);
			// i - 1 + (end != boss) + (start != boss) <= sum_others + j
			if(info.first - 1 + (end != boss) + (start != boss) <= sum_others + j) {
				int i = min(info.second, sum_others - j + 1 - (end != boss) - (start != boss));
				min_self(heur, info.value - i * penalty + diff[j] + cool_answer);
			}
		}
		debug() << imie(heur) imie(answer);
		assert(heur == answer);*/
	// }
	
	
	
	// for(int i = 0; i < (int) diff.size(); ++i) {
		// int j = perfect - lacks + i;
		// if(0 <= j && j < (int) me.size() && me[j] != INF) {
			// min_self(answer, diff[i] + me[j]);
		// }
	// }
	// return answer;
	
	/*
	// cerr << cnt << endl;
	// 2 * jem + (start != i) + (end != i) - 1 <= sum_jem
	#define dp other_dp
	vector<vector<ll>> dp(big + 1, vector<ll>(big + 1, INF));
	dp[0][0] = 0; // dp[max_jem][sum_jem]
	for(int i = 0; i < n; ++i) {
		const vector<long long>& row = values[i];
		vector<vector<ll>> new_dp(big + 1, vector<ll>(big + 1, INF));
		for(int max_jem = 0; max_jem <= big; ++max_jem) {
			for(int sum_jem = 0; sum_jem <= big; ++sum_jem) {
				long long me = dp[max_jem][sum_jem];
				if(me == INF) {
					continue;
				}
				for(int j = 0; j < (int) row.size(); ++j) {
					if(row[j] != INF) {
						int special = 2 * j + (start != i) + (end != i) - 1;
						min_self(new_dp[max(max_jem, special)][min(big, sum_jem + j)], me + row[j]);
					}
				}
			}
		}
		dp = new_dp;
	}
	long long best = INF;
	for(int max_jem = 0; max_jem <= big; ++max_jem) {
		for(int sum_jem = max_jem; sum_jem <= big; ++sum_jem) {
			// debug() << ">>>>>>>>>>>>>>>>>>>>" imie(max_jem) imie(sum_jem) imie(dp[max_jem][sum_jem]);
			best = min(best, dp[max_jem][sum_jem]);
		}
	}
	debug() << imie(start) imie(end) imie(best);
	return best;
	// return rec(values, {}, 0LL, start, end);
	*/
}

void test_case() {
	int n;
	scanf("%d", &n);
	vector<Row> all;
	for(int i = 0; i < n; ++i) {
		OldRow tmp;
		Row row = tmp.read();
		if(!row.empty()) {
			// debug() << imie(row);
			all.push_back(row);
		}
	}
	// debug() << all;
	if(all.empty()) {
		puts("0");
		return;
	}
	n = all.size();
	long long answer = INF;
	
	for(const Row& row : all) {
		long long his_sum = 0;
		for(const Block& block : row.blocks) {
			his_sum += block.total;
		}
		min_self(answer, his_sum);
	}
	
	for(int i = 0; i < (int) all.size(); ++i) {
		all[i].id = i;
	}
	// candidates.clear();
	
	v_cand.clear();
	s_cand.clear();
	
	// for(int start = 0; start < 1; ++start) {
		// candidates.push_back(all[start].id);
		// vector<Row> new_all;
		// int nxt = start;
		// for(int i = 0; i < n; ++i) {
			// Row row = all[i];
			// assert(!row.empty());
			// if(i != start && row.first_write) {
				// row.skip();
			// }
			// if(i == start) {
				// assert(!row.empty());
			// }
			// if(!row.empty()) {
				// new_all.push_back(row);
			// }
			// else if(i < start) {
				// nxt--;
			// }
		// }
		// solve(new_all, nxt, -1);
	// }
	// debug() << imie(candidates);
	
	
	
	// for(int rep = 0; rep < 2; ++rep) {
		// vector<pair<long long, int>> they;
		// for(int i = 0; i < n; ++i) {
			// if(all[i].first_write == rep) {
				// they.emplace_back(all[i].blocks.back().just, all[i].id);
			// }
		// }
		// sort(they.begin(), they.end());
		// they.resize(min(n, (int) they.size()));
		// for(auto pp : they) {
			// candidates.push_back(pp.second);
		// }
	// }
	
	set<int> starts, ends;
	
	for(int rep = 0; rep < 2; ++rep) {
	// {
		vector<pair<long long, int>> they;
		for(int i = 0; i < n; ++i) {
			if(all[i].first_write == rep) {
				they.emplace_back(all[i].blocks.back().just, i);
			}
		}
		sort(they.begin(), they.end());
		
		for(int who = 0; who < min(3, (int) they.size()); ++who) { // maybe should be 2?
			int start = they[who].second;
			starts.insert(start);
		}
	}
	// for(int i = 0; i < n; ++i) {
		// debug() << imie(all[i].blocks[0].total) imie(all[i].blocks[0].just);
	// }
	
	// TODO, add 
	
	// for(int rep = 0; rep < 2; ++rep) {
		for(int r : {0, 1}) {
		// {
			vector<pair<long long, int>> they;
			for(int i = 0; i < n; ++i) {
				if(all[i].first_write && all[i].blocks.size() == 1) {
					continue;
				}
				// if(all[i].first_write == rep) {
					ll A = all[i].blocks[0].total;
					ll B = all[i].blocks[0].just;
					if(r == (A == B)) {
					// if(r) { //if(r){
						they.emplace_back(A, i);
					}
					else {
						they.emplace_back(A - B, i);
					}
					// they.emplace_back(all[i].blocks[0].total, i);
				// }
			}
			sort(they.begin(), they.end());
			debug() << imie(they);
			
			for(int who = 0; who < min(3, (int) they.size()); ++who) { // maybe should be 2?
				int start = they[who].second;
				ends.insert(start);
			}
		}
		// }
	// }
	// for(int i = 0; i < n; ++i) {
		// if(find(candidates.begin(), candidates.end(), all[i].id) != candidates.end()) {
			// ends.insert(i);
			// starts.insert(i);
		// }
	// }
	debug() << imie(starts) imie(ends) imie(n);
	// cerr << starts.size() << "/" << n << endl;
	
	set<pair<int,int>> done;
	int PAIRS = 0;
	auto consider = [&](int start_id, int end_id) {
		if(PAIRS >= 100 || done.count(make_pair(start_id, end_id))) {
			return;
		}
		++PAIRS;
		done.insert(make_pair(start_id, end_id));
		vector<Row> new_all;
		for(Row row : all) {
			if(row.id != start_id && row.first_write) {
				row.skip();
			}
			if(!row.empty()) {
				new_all.push_back(row);
			}
		}
		auto where = [&](int id) {
			for(int i = 0; i < (int) new_all.size(); ++i) {
				if(new_all[i].id == id) {
					return i;
				}
			}
			return -1;
		};
		int s = where(start_id);
		int e = where(end_id);
		assert(s != -1);
		if(s != -1 && e != -1) {
			// debug() << imie(start) imie(nxt) imie(end) imie(actually);
			// int actually = end;
			if(s != e || (int) new_all[s].blocks.size() >= 2) {
				long long maybe = solve(new_all, s, e);
				debug() << imie(start_id) imie(end_id) imie(maybe);
				answer = min(answer, maybe);
			}
		}
	};
	
	if(n <= 5) {
		for(int i = 0; i < n; ++i) {
			starts.insert(i);
			ends.insert(i);
		}
	}
	
	for(int s : starts) {
		for(int e : ends) {
			consider(all[s].id, all[e].id);
		}
	}
	for(int i = 0; i < (int) v_cand.size(); ++i) {
		for(int s : starts) {
			consider(all[s].id, v_cand[i]);
		}
		for(int e : ends) {
			consider(v_cand[i], all[e].id);
		}
		for(int j = 0; j <= i; ++j) {
			consider(v_cand[i], v_cand[j]);
			consider(v_cand[j], v_cand[i]);
		}
	}
	// if((int) candidates.size() >= 3) {
		// cerr << "candidates SIZE = " << candidates.size() << endl;
	// }
	// assert((int) candidates.size() <= 3);
	
	// if(PAIRS >= 37) {
		// for(int rep = 0; rep < 5; ++rep) {
			// cerr << PAIRS << endl;
		// }
	// }
	// assert(PAIRS <= 50);
	
	// for(int start = 0; start < n; ++start) {
	/*for(int start : starts) {
		vector<Row> new_all;
		int nxt = start;
		for(int i = 0; i < n; ++i) {
			Row row = all[i];
			assert(!row.empty());
			if(i != start && row.first_write) {
				row.skip();
			}
			if(i == start) {
				assert(!row.empty());
			}
			if(!row.empty()) {
				new_all.push_back(row);
			}
			else if(i < start) {
				nxt--;
			}
		}
		assert(!new_all.empty());
		// for(int end = 0; end < (int) new_all.size(); ++end) {
		for(int end : ends) {
			int actually = -1;
			for(int i = 0; i < (int) new_all.size(); ++i) {
				if(new_all[i].id == all[end].id) {
					actually = i;
				}
			}
			if(actually == -1) {
				continue;
			}
			debug() << imie(start) imie(nxt) imie(end) imie(actually);
			// int actually = end;
			long long maybe = solve(new_all, nxt, actually);
			debug() << imie(start) imie(end) imie(nxt) imie(actually) imie(maybe);
			answer = min(answer, maybe);
		}
	}*/
	
	printf("%lld\n", answer);
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		test_case();
	}
}