```go
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 0, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	var readInt = func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	s := readInt()
	m := readInt()
	k := readInt()

	a := make([]int, n+1)
	uniqueA := make([]int, 0, n)
	freq := make(map[int]bool)

	for i := 1; i <= n; i++ {
		a[i] = readInt()
		if !freq[a[i]] {
			freq[a[i]] = true
			uniqueA = append(uniqueA, a[i])
		}
	}

	sort.Ints(uniqueA)

	Ls := make([]int, s)
	Rs := make([]int, s)
	for i := 0; i < s; i++ {
		Ls[i] = readInt()
		Rs[i] = readInt()
	}

	var log2 [1505]int
	for i := 2; i <= n+1; i++ {
		log2[i] = log2[i/2] + 1
	}

	B := make([]int, n+1)
	P := make([]int, n+1)
	dp := make([]int, n+1)
	st := make([][12]int, n+1)
	pref := make([]int, n+1)
	val := make([]int, n+1)
	nextDp := make([]int, n+1)

	check := func(V int) bool {
		for i := 1; i <= n; i++ {
			if a[i] <= V {
				B[i] = 1
			} else {
				B[i] = 0
			}
			P[i] = P[i-1] + B[i]
		}

		for i := 0; i <= n; i++ {
			dp[i] = -1e9
		}
		dp[0] = 0

		maxCov := 0

		for j := 1; j <= m; j++ {
			pref[0] = dp[0]
			for i := 1; i <= n; i++ {
				pref[i] = pref[i-1]
				if dp[i] > pref[i] {
					pref[i] = dp[i]
				}
			}

			for i := 0; i <= n; i++ {
				if dp[i] != -1e9 {
					val[i] = dp[i] - P[i]
				} else {
					val[i] = -1e9
				}
				st[i][0] = val[i]
				nextDp[i] = -1e9
			}

			for step := 1; (1 << step) <= n+1; step++ {
				for i := 0; i+(1<<step) <= n+1; i++ {
					aVal := st[i][step-1]
					bVal := st[i+(1<<(step-1))][step-1]
					if aVal > bVal {
						st[i][step] = aVal
					} else {
						st[i][step] = bVal
					}
				}
			}

			query := func(L, R int) int {
				if L > R {
					return -1e9
				}
				step := log2[R-L+1]
				aVal := st[L][step]
				bVal := st[R-(1<<step)+1][step]
				if aVal > bVal {
					return aVal
				}
				return bVal
			}

			for i := 0; i < s; i++ {
				LIdx := Ls[i]
				RIdx := Rs[i]

				v1 := int(-1e9)
				if pref[LIdx-1] != -1e9 {
					v1 = pref[LIdx-1] - P[LIdx-1]
				}
				v2 := query(LIdx, RIdx)

				best := v1
				if v2 > best {
					best = v2
				}

				if best != -1e9 {
					if best+P[RIdx] > nextDp[RIdx] {
						nextDp[RIdx] = best + P[RIdx]
					}
				}
			}

			for i := 0; i <= n; i++ {
				dp[i] = nextDp[i]
				if dp[i] > maxCov {
					maxCov = dp[i]
				}
			}
		}

		return maxCov >= k
	}

	ans := -1
	low := 0
	high := len(uniqueA) - 1

	for low <= high {
		mid := (low + high) / 2
		V := uniqueA[mid]
		if check(V) {
			ans = V
			high = mid - 1
		} else {
			low = mid + 1
		}
	}

	fmt.Println(ans)
}
```