```go
package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	t := nextInt(scanner)
	for tc := 0; tc < t; tc++ {
		n := nextInt(scanner)
		m := nextInt(scanner)
		k := nextInt(scanner)
		d := nextInt(scanner)

		rowCosts := make([]int64, n)
		for i := 0; i < n; i++ {
			row := make([]int, m)
			for j := 0; j < m; j++ {
				row[j] = nextInt(scanner)
			}
			rowCosts[i] = solveRow(row, m, d)
		}

		var res int64 = 0
		for i := 0; i < k; i++ {
			res += rowCosts[i]
		}
		cur := res
		for i := k; i < n; i++ {
			cur += rowCosts[i] - rowCosts[i-k]
			if cur < res {
				res = cur
			}
		}
		writer.WriteString(strconv.FormatInt(res, 10))
		writer.WriteByte('\n')
	}
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	b := scanner.Bytes()
	x := 0
	for i := 0; i < len(b); i++ {
		x = x*10 + int(b[i]-'0')
	}
	return x
}

func solveRow(row []int, m, d int) int64 {
	dp := make([]int64, m)
	dq := make([]int, 0, m)

	dp[0] = int64(row[0] + 1)
	dq = append(dq, 0)

	maxJump := d + 1

	for i := 1; i < m; i++ {
		for len(dq) > 0 && dq[0] < i-maxJump {
			dq = dq[1:]
		}

		dp[i] = int64(row[i]+1) + dp[dq[0]]

		for len(dq) > 0 && dp[i] <= dp[dq[len(dq)-1]] {
			dq = dq[:len(dq)-1]
		}
		dq = append(dq, i)
	}

	return dp[m-1]
}
```