#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int N = 1e6 + 5, INF = 1e9;

struct atom {
	int l, r, dp;
	atom (int a = 0, int b = 0, int c = 0) : l(a), r(b), dp(c) {}
};

vector <atom> seq, nseq;
vector <int> a[N];
set <pii> all;
int s[N], sum[N], pre[N], nxt[N], c[N], dp[N];
int T, n, m, top;

bool cmpl(atom a, atom b) {
	if (a.l != b.l) return a.l > b.l;
	if (a.r != b.r) return a.r < b.r;
	return a.dp < b.dp;
}

struct node_t {
	int l, r, mx, mn, tag, ans;
} p[N << 2];

void update(int u) {
	p[u].mx = p[u << 1].mx;
	p[u].mn = p[u << 1 | 1].mn;
	p[u].ans = min(p[u << 1].ans, p[u << 1 | 1].ans);
}

void add_tag(int u, int x) {
	p[u].mx += x;
	p[u].mn += x;
	p[u].tag += x;
	p[u].ans += x;
}

void pushdown(int u) {
	if (p[u].tag) {
		add_tag(u << 1, p[u].tag);
		add_tag(u << 1 | 1, p[u].tag);
		p[u].tag = 0;
	}
}

void build(int u, int l, int r) {
	p[u].l = l; p[u].r = r; p[u].tag = 0;
	p[u].mx = p[u].mn = p[u].ans = INF;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	update(u);
}

// [l, r] min = x
void change(int u, int l, int r, int x) {
	if (p[u].mx <= x) return;
	if (l <= p[u].l && p[u].r <= r) {
		if (p[u].mx == p[u].mn) {
			add_tag(u, x - p[u].mx);
			return;
		}
		pushdown(u);
		change(u << 1, l, r, x);
		change(u << 1 | 1, l, r, x);
		update(u);
		return;
	}
	pushdown(u);
	int mid = (p[u].l + p[u].r) >> 1;
	if (mid >= l) change(u << 1, l, r, x);
	if (mid + 1 <= r) change(u << 1 | 1, l, r, x);
	update(u);
}

int query(int u, int l, int r) {
	if (l <= p[u].l && p[u].r <= r) return p[u].ans;
	pushdown(u);
	int mid = (p[u].l + p[u].r) >> 1, ans = INF;
	if (mid >= l) ans = min(ans, query(u << 1, l, r));
	if (mid + 1 <= r) ans = min(ans, query(u << 1 | 1, l, r));
	return ans;
}

// ans[x] += y
void modify(int u, int x, int y) {
	if (p[u].l == p[u].r) {
		p[u].ans += y;
		return;
	}
	pushdown(u);
	int mid = (p[u].l + p[u].r) >> 1;
	if (mid >= x) modify(u << 1, x, y);
	else modify(u << 1 | 1, x, y);
	update(u);
}

int main() {
#ifdef xay5421
	freopen("b.in","r",stdin);
#endif
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &m, &n);
		for (int i = 1; i <= m; i++) scanf("%d", &c[i]);
		for (int i = 1; i <= n; i++) {
			a[i].resize(m + 1);
			for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
		}
		seq.clear();
		for (int i = 1; i <= m; i++) {
			if (!a[n][i]) seq.push_back(atom(i, i, a[n][i]));
		}
		for (int i = n - 1; i >= 2; i--) {
			nseq.clear();
			for (int j = 1; j <= m; j++) {
				s[j] = s[j - 1] + (a[i][j] == 0);
				sum[j] = sum[j - 1] + a[i][j];
				if (a[i][j] == 0) {
					pre[j] = j;
				} else {
					pre[j] = pre[j - 1];
				}
			}
			nxt[m + 1] = 0;
			for (int j = m; j >= 1; j--) {
				if (a[i][j] == 0) {
					nxt[j] = j;
				} else {
					nxt[j] = nxt[j + 1];
				}
			}
			for (auto j : seq) {
				if (s[j.r] - s[j.l - 1]) {
					nseq.push_back(atom(j.l, j.r, j.dp + sum[j.r] - sum[j.l - 1]));
				} else {
					auto ins = [&](int l, int r, int dp) {
						nseq.push_back(atom(l, r, dp + sum[r] - sum[l - 1]));
					};
					if (pre[j.l]) ins(pre[j.l], j.r, j.dp);
					if (nxt[j.r]) ins(j.l, nxt[j.r], j.dp);
				}
			}
			sort(nseq.begin(), nseq.end(), cmpl);
			all.clear(); seq.clear();
			for (auto j : nseq) {
				auto it = all.upper_bound(make_pair(j.r, INF));
				if (it == all.begin()) {
					all.insert(make_pair(j.r, j.dp));
					seq.push_back(j);
					continue;
				}
				--it;
				if (it -> second <= j.dp) continue;
				seq.push_back(j);
				if (it -> first == j.r) all.erase(it);
				all.insert(make_pair(j.r, j.dp));
				it = all.find(make_pair(j.r, j.dp));
				while (it != all.end()) {
					auto it2 = it; ++it2;
					if (it2 -> second >= j.dp) {
						all.erase(it2);
					} else {
						break;
					}
				}
			}
		}
		int flag = 0;
		for (int i = 1; i <= m; i++) {
			sum[i] = sum[i - 1] + a[1][i];
			if (c[i] && a[1][i]) {
				flag = 1;
				break;
			}
		}
		if (flag) {
			printf("-1\n");
			continue;
		}
		sort(seq.begin(), seq.end(), cmpl);
		// for (auto i : seq) fprintf(stderr, "%d %d %d\n", i.l, i.r, i.dp);
		build(1, 1, m);
		dp[m + 1] = 0;
		for (int i = m, j = 0; i >= 1; i--) {
			if (!c[i]) dp[i] = dp[i + 1];
			else dp[i] = INF;
			while (j < (int)seq.size() && seq[j].l == i) {
				change(1, seq[j].r, m, seq[j].dp);
				// fprintf(stderr, "l = %d, r = %d, dp = %d\n", seq[j].l, seq[j].r, seq[j].dp);
				++j;
			}
			modify(1, i, dp[i + 1] + sum[i]);
			// fprintf(stderr, "i = %d, val = %d\n", i, dp[i + 1] + sum[i]);
			// fprintf(stderr, "dp[%d] = %d\n", i, dp[i]);
			if (p[1].ans != INF) dp[i] = min(dp[i], query(1, i, m) - sum[i - 1]);
		}
		if (dp[1] >= INF) printf("%d\n", -1);
		else printf("%d\n", dp[1]);
	}
	return 0;
}