```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

// Col struct to store original index and value
type Col struct {
	id int
	a  int
}

// Seg struct to store segment length and number of occurrences
type Seg struct {
	l     int
	count int64
}

func main() {
	// Use buffered I/O for speed
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	for i := 0; i < t; i++ {
		solve(reader, writer)
	}
}

func solve(r *bufio.Reader, w *bufio.Writer) {
	var n int
	fmt.Fscan(r, &n)

	cols := make([]Col, n)
	for i := 0; i < n; i++ {
		var a int
		fmt.Fscan(r, &a)
		cols[i] = Col{id: i + 1, a: a} // Use 1-based indexing for logic
	}

	var m int64
	fmt.Fscan(r, &m)

	// Sort columns by the number of black cells (height)
	sort.Slice(cols, func(i, j int) bool {
		return cols[i].a < cols[j].a
	})

	// DSU initialization
	parent := make([]int, n+2)
	sz := make([]int, n+2)
	born := make([]int, n+2)
	active := make([]bool, n+2)

	for i := 1; i <= n; i++ {
		parent[i] = i
		sz[i] = 1
		born[i] = 0
		active[i] = false
	}

	// Map to aggregate counts of segments by length
	segCounts := make(map[int]int64)

	// Iterative Find with path compression
	var find func(int) int
	find = func(i int) int {
		root := i
		for parent[root] != root {
			root = parent[root]
		}
		// Path compression
		curr := i
		for curr != root {
			next := parent[curr]
			parent[curr] = root
			curr = next
		}
		return root
	}

	// Union function
	union := func(i, j, time int) {
		rootI := find(i)
		rootJ := find(j)
		if rootI != rootJ {
			// Record the lifetime of the component rooted at rootI
			durI := time - born[rootI]
			if durI > 0 {
				segCounts[sz[rootI]] += int64(durI)
			}
			// Record the lifetime of the component rooted at rootJ
			durJ := time - born[rootJ]
			if durJ > 0 {
				segCounts[sz[rootJ]] += int64(durJ)
			}
			
			// Merge I into J
			parent[rootI] = rootJ
			sz[rootJ] += sz[rootI]
			born[rootJ] = time
		}
	}

	// Process columns in order of height
	for i := 0; i < n; {
		h := cols[i].a
		
		// If height is n, these columns are fully black and contribute no white cells
		if h == n {
			break
		}

		// Activate all columns with the current height h
		j := i
		for j < n && cols[j].a == h {
			c := cols[j].id
			active[c] = true
			born[c] = h
			
			// Try to union with left neighbor
			if c > 1 && active[c-1] {
				union(c-1, c, h)
			}
			// Try to union with right neighbor
			if c < n && active[c+1] {
				union(c, c+1, h)
			}
			j++
		}
		i = j
	}

	// Collect segments that remain active until the bottom of the matrix
	for i := 1; i <= n; i++ {
		if active[i] && parent[i] == i {
			dur := n - born[i]
			if dur > 0 {
				segCounts[sz[i]] += int64(dur)
			}
		}
	}

	// Convert map to slice for sorting
	segments := make([]Seg, 0, len(segCounts))
	for l, c := range segCounts {
		segments = append(segments, Seg{l: l, count: c})
	}

	// Sort segments by length descending
	sort.Slice(segments, func(i, j int) bool {
		return segments[i].l > segments[j].l
	})

	// Greedy allocation
	var beauty int64 = 0
	for _, s := range segments {
		if m <= 0 {
			break
		}
		length := int64(s.l)
		
		// Number of cells required to take all segments of this type
		totalCells := s.count * length
		
		if m >= totalCells {
			// Take all segments of this length
			beauty += s.count * (length - 1)
			m -= totalCells
		} else {
			// Take as many full segments as possible
			count := m / length
			beauty += count * (length - 1)
			m -= count * length
			
			// If there are remaining cells, take a partial segment
			if m > 0 {
				beauty += m - 1
				m = 0
			}
		}
	}

	fmt.Fprintln(w, beauty)
}
```