package main

import (
	"bytes"
	"io"
	"os"
	"sort"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c > ' ' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return val * sign
}

type HeapNode struct {
	d int64
	v int
}

type MinHeap struct {
	a []HeapNode
}

func (h *MinHeap) Len() int {
	return len(h.a)
}

func (h *MinHeap) Push(v int, d int64) {
	x := HeapNode{d: d, v: v}
	h.a = append(h.a, x)
	i := len(h.a) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if h.a[p].d <= x.d {
			break
		}
		h.a[i] = h.a[p]
		i = p
	}
	h.a[i] = x
}

func (h *MinHeap) Pop() (int, int64) {
	x := h.a[0]
	last := h.a[len(h.a)-1]
	h.a = h.a[:len(h.a)-1]
	if len(h.a) > 0 {
		i := 0
		for {
			l := i*2 + 1
			if l >= len(h.a) {
				break
			}
			r := l + 1
			c := l
			if r < len(h.a) && h.a[r].d < h.a[l].d {
				c = r
			}
			if h.a[c].d >= last.d {
				break
			}
			h.a[i] = h.a[c]
			i = c
		}
		h.a[i] = last
	}
	return x.v, x.d
}

func main() {
	fs := NewFastScanner()
	t := fs.NextInt()
	var out bytes.Buffer
	out.Grow(t * 24)

	for ; t > 0; t-- {
		n := fs.NextInt()
		m := fs.NextInt()

		cost := make([]int, n)
		for i := 0; i < n; i++ {
			cost[i] = fs.NextInt()
		}

		attr := make([]int, n*m)
		for i := 0; i < n; i++ {
			base := i * m
			for j := 0; j < m; j++ {
				attr[base+j] = fs.NextInt()
			}
		}

		p := n * m
		nodes := n + 2*p
		edges := 5*p - 2*m

		head := make([]int, nodes)
		for i := 0; i < nodes; i++ {
			head[i] = -1
		}
		to := make([]int, edges)
		next := make([]int, edges)
		wt := make([]int64, edges)
		ep := 0

		addEdge := func(u, v int, w int64) {
			to[ep] = v
			next[ep] = head[u]
			wt[ep] = w
			head[u] = ep
			ep++
		}

		ord := make([]int, n)
		curID := n

		for j := 0; j < m; j++ {
			for i := 0; i < n; i++ {
				ord[i] = i
			}
			jj := j
			sort.Slice(ord, func(a, b int) bool {
				ia := ord[a]
				ib := ord[b]
				va := attr[ia*m+jj]
				vb := attr[ib*m+jj]
				if va != vb {
					return va < vb
				}
				return ia < ib
			})

			baseV := curID
			baseS := curID + n
			curID += 2 * n

			prevVal := 0
			for pos := 0; pos < n; pos++ {
				idx := ord[pos]
				val := attr[idx*m+j]
				vID := baseV + pos
				sID := baseS + pos

				addEdge(idx, vID, 0)
				addEdge(vID, sID, 0)
				addEdge(sID, idx, int64(cost[idx]))

				if pos > 0 {
					addEdge(vID, vID-1, int64(val-prevVal))
				}
				if pos+1 < n {
					addEdge(sID, sID+1, 0)
				}
				prevVal = val
			}
		}

		const INF int64 = 1<<62
		dist := make([]int64, nodes)
		for i := 0; i < nodes; i++ {
			dist[i] = INF
		}
		dist[0] = 0

		h := MinHeap{a: make([]HeapNode, 0, n)}
		h.Push(0, 0)

		target := n - 1
		for h.Len() > 0 {
			v, d := h.Pop()
			if d != dist[v] {
				continue
			}
			if v == target {
				break
			}
			for e := head[v]; e != -1; e = next[e] {
				nv := to[e]
				nd := d + wt[e]
				if nd < dist[nv] {
					dist[nv] = nd
					h.Push(nv, nd)
				}
			}
		}

		out.WriteString(strconv.FormatInt(dist[target], 10))
		out.WriteByte('\n')
	}

	os.Stdout.Write(out.Bytes())
}