package main

import (
	"bufio"
	"io"
	"math/bits"
	"os"
	"sort"
	"strconv"
)

type Pair struct {
	sum  int64
	cost int64
}

const INF int64 = 1 << 60

func mulMatrix(a, b [][]int64, n int) [][]int64 {
	res := make([][]int64, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int64, n)
		for j := 0; j < n; j++ {
			res[i][j] = INF
		}
	}
	for i := 0; i < n; i++ {
		ri := res[i]
		for k := 0; k < n; k++ {
			av := a[i][k]
			if av >= INF {
				continue
			}
			bk := b[k]
			for j := 0; j < n; j++ {
				bv := bk[j]
				if bv >= INF {
					continue
				}
				v := av + bv
				if v < ri[j] {
					ri[j] = v
				}
			}
		}
	}
	return res
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	nextInt := func() int64 {
		for p < len(data) && data[p] <= ' ' {
			p++
		}
		sign := int64(1)
		if data[p] == '-' {
			sign = -1
			p++
		}
		var x int64
		for p < len(data) && data[p] > ' ' {
			x = x*10 + int64(data[p]-'0')
			p++
		}
		return x * sign
	}

	n := int(nextInt())
	m := int(nextInt())
	q := int(nextInt())
	s := int(nextInt()) - 1

	a := make([]int64, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}

	adj := make([][]int, n)
	inAdj := make([][]int, n)
	for i := 0; i < m; i++ {
		v := int(nextInt()) - 1
		u := int(nextInt()) - 1
		adj[v] = append(adj[v], u)
		inAdj[u] = append(inAdj[u], v)
	}

	queries := make([]int64, q)
	var maxC int64
	for i := 0; i < q; i++ {
		queries[i] = nextInt()
		if queries[i] > maxC {
			maxC = queries[i]
		}
	}

	sizeMask := 1 << n
	allMask := sizeMask - 1
	totalStates := sizeMask * n

	sumMask := make([]int64, sizeMask)
	for mask := 1; mask < sizeMask; mask++ {
		lsb := mask & -mask
		b := bits.TrailingZeros(uint(lsb))
		sumMask[mask] = sumMask[mask^lsb] + a[b]
	}
	A := sumMask[allMask]

	maskOf := make([]int, totalStates)
	nodeOf := make([]int, totalStates)
	for mask := 0; mask < sizeMask; mask++ {
		base := mask * n
		for v := 0; v < n; v++ {
			idx := base + v
			maskOf[idx] = mask
			nodeOf[idx] = v
		}
	}

	M := make([][]int64, n)
	partSums := make([][]int64, n)
	partSuf := make([][]int64, n)

	queue := make([]int, totalStates)
	distState := make([]int32, totalStates)
	bestMask := make([]int32, sizeMask)

	for st := 0; st < n; st++ {
		for i := 0; i < totalStates; i++ {
			distState[i] = -1
		}
		for i := 0; i < sizeMask; i++ {
			bestMask[i] = -1
		}

		startMask := 1 << st
		startIdx := startMask*n + st
		distState[startIdx] = 0

		head, tail := 0, 0
		queue[tail] = startIdx
		tail++

		for head < tail {
			idx := queue[head]
			head++
			d := distState[idx]
			mask := maskOf[idx]
			if bestMask[mask] == -1 || d < bestMask[mask] {
				bestMask[mask] = d
			}
			v := nodeOf[idx]
			nd := d + 1
			for _, u := range adj[v] {
				nmask := mask | (1 << u)
				nidx := nmask*n + u
				if distState[nidx] == -1 {
					distState[nidx] = nd
					queue[tail] = nidx
					tail++
				}
			}
		}

		row := make([]int64, n)
		for j := 0; j < n; j++ {
			needMask := allMask ^ (1 << j)
			base := needMask * n
			best := INF
			for _, v := range inAdj[j] {
				d := distState[base+v]
				if d >= 0 {
					cand := int64(d) + 1
					if cand < best {
						best = cand
					}
				}
			}
			row[j] = best
		}
		M[st] = row

		pairs := make([]Pair, 0, sizeMask)
		for mask := 0; mask < sizeMask; mask++ {
			d := bestMask[mask]
			if d >= 0 {
				pairs = append(pairs, Pair{sumMask[mask], int64(d)})
			}
		}

		sort.Slice(pairs, func(i, j int) bool {
			if pairs[i].sum == pairs[j].sum {
				return pairs[i].cost < pairs[j].cost
			}
			return pairs[i].sum < pairs[j].sum
		})

		sums := make([]int64, 0, len(pairs))
		costs := make([]int64, 0, len(pairs))
		for _, pr := range pairs {
			if len(sums) > 0 && sums[len(sums)-1] == pr.sum {
				if pr.cost < costs[len(costs)-1] {
					costs[len(costs)-1] = pr.cost
				}
			} else {
				sums = append(sums, pr.sum)
				costs = append(costs, pr.cost)
			}
		}

		suf := make([]int64, len(costs))
		for i := len(costs) - 1; i >= 0; i-- {
			if i == len(costs)-1 || costs[i] < suf[i+1] {
				suf[i] = costs[i]
			} else {
				suf[i] = suf[i+1]
			}
		}

		partSums[st] = sums
		partSuf[st] = suf
	}

	var maxT int64
	for i := 0; i < q; i++ {
		t := (queries[i] - 1) / A
		if t > maxT {
			maxT = t
		}
	}

	maxPow := 1
	for (int64(1) << uint(maxPow)) <= maxT {
		maxPow++
	}

	powers := make([][][]int64, maxPow)
	powers[0] = make([][]int64, n)
	for i := 0; i < n; i++ {
		powers[0][i] = append([]int64(nil), M[i]...)
	}
	for i := 1; i < maxPow; i++ {
		powers[i] = mulMatrix(powers[i-1], powers[i-1], n)
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	for _, C := range queries {
		t := (C - 1) / A
		need := C - t*A

		cur := make([]int64, n)
		tmp := make([]int64, n)
		for i := 0; i < n; i++ {
			cur[i] = INF
			tmp[i] = INF
		}
		cur[s] = 0

		bit := 0
		for tt := t; tt > 0; tt >>= 1 {
			if tt&1 == 1 {
				for j := 0; j < n; j++ {
					tmp[j] = INF
				}
				mat := powers[bit]
				for i := 0; i < n; i++ {
					if cur[i] >= INF {
						continue
					}
					ci := cur[i]
					row := mat[i]
					for j := 0; j < n; j++ {
						if row[j] >= INF {
							continue
						}
						v := ci + row[j]
						if v < tmp[j] {
							tmp[j] = v
						}
					}
				}
				cur, tmp = tmp, cur
			}
			bit++
		}

		ans := INF
		for j := 0; j < n; j++ {
			if cur[j] >= INF {
				continue
			}
			sums := partSums[j]
			suf := partSuf[j]
			l, r := 0, len(sums)
			for l < r {
				mid := (l + r) >> 1
				if sums[mid] >= need {
					r = mid
				} else {
					l = mid + 1
				}
			}
			v := cur[j] + suf[l]
			if v < ans {
				ans = v
			}
		}

		out.WriteString(strconv.FormatInt(ans, 10))
		out.WriteByte('\n')
	}
	out.Flush()
}