L. Badminton
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The better a person plays badminton, the higher the requirements for badminton rackets will be. Joey is looking at a badminton racket now and evaluating who it is suitable for.

The strings on a badminton racket can be described as a graph with $$$n$$$ nodes and $$$m$$$ directed edges. Each node $$$i$$$ has an elasticity value $$$a_i$$$ and toughness value $$$b_i$$$.

A badminton player's ability can be represented by an integer $$$A$$$. When he uses the badminton racket, all nodes $$$i$$$ with $$$a_i\leq A$$$ will be considered activated, and other nodes will be considered inactive. Let $$$s_i=1$$$ represent node $$$i$$$ is activated, and $$$s_i=0$$$ represent node $$$i$$$ is inactive.

When a badminton racket is used, each node $$$i$$$ has a pressure value $$$p_i$$$. The definition of $$$p_i$$$ is as follows:

$$$$$$p_i = \max_{\substack{\pi = (v_1, v_2, \dots, v_q) \\ v_q = i}} \left( \sum_{\substack{\exists t \in [1,q] : v_t = k}} s_{k}a_{k} \right)$$$$$$

$$$\pi$$$ is a path in the directed graph, $$$v_1, v_2, \dots, v_q$$$ are $$$q$$$ points in sequence on the path(the same point or path can be passed through repeatedly). Therefore, this definition means that $$$p_i$$$ is equal to the maximum sum of $$$s_ka_k$$$ ​​of all nodes $$$k$$$ among all paths ending with $$$i$$$.

If each node $$$i$$$ satisfies $$$p_i\leq b_i$$$, then this badminton racket is suitable for this badminton player.

Joey wants to know what the maximum $$$A$$$ a badminton player can have. (note that this badminton racket should be suitable for this player)

Input

The first line contains two integers $$$n$$$ and $$$m(1\leq n,m\leq 10^5)$$$, the number of nodes and edges.

The second line contains $$$n$$$ integers, and the $$$i$$$-th integer $$$a_i(1\leq a_i\leq 10^9)$$$ represents the elasticity value of node $$$i$$$.

The third line contains $$$n$$$ integers, and the $$$i$$$-th integer $$$b_i(1\leq b_i\leq 10^9)$$$ represents the toughness value of node $$$i$$$.

For the next $$$m$$$ lines, each line contains $$$2$$$ integers $$$u,v(1\leq u,v\leq n)$$$, which represents a directed edge from $$$u$$$ to $$$v$$$.

Output

Output the largest $$$A$$$ the badminton player can have, if $$$A$$$ can be larger than $$$10^9$$$ then output $$$10^9$$$.

Example
Input
5 10
10 1 3 5 6
9 9 5 10 14
1 5
4 2
4 2
2 2
5 1
5 1
3 4
4 1
1 1
3 4
Output
5