Maximum People Carry

You are given a network of N cities. Each city i has a population P_i. There are bidirectional roads connecting these cities such that there is a path between any two cities. A tourist wants to travel from city A to city B and carry as many people as possible along the route. However, the tourist has a bag that can only carry a limited weight (i.e. at most W people). In addition, the number of people available along the chosen route is limited by the smallest city population encountered on that route.

Your task is to determine the maximum number of people the tourist can carry from city A to city B. Mathematically, if the path from A to B is given by a sequence of cities, then the answer is given by:

[ \text{Answer} = \min\Big( W, \min_{i \in \text{path}}{P_i} \Big) ]

It is guaranteed that there exists a valid path between A and B.

inputFormat

The input is given on standard input and has the following format:

1. An integer N representing the number of cities.
2. A line with N integers, where the i-th integer represents the population of city i.
3. A line with three integers: A, B and W, where A is the starting city, B is the destination city, and W is the maximum weight capacity.
4. An integer R indicating the number of roads.
5. R lines follow, each containing two integers u and v representing a bidirectional road connecting city u and city v.

Note: Cities are numbered from 1 to N.

outputFormat

Output a single integer on standard output: the maximum number of people the tourist can carry from city A to city B.

5
10 20 30 40 50
2 4 25
4
1 2
2 3
3 4
4 5

20