B'Jellyfish loves playing a game called "Inscryption" which is played on a directed acyclic graph with n vertices and m edges. All edges a to b satisfy a < b . You need to move from vertex 1 to vertex n along the directed edges, and then fight with the final boss. You will collect cards and props in the process. Each card has two attributes: HP and damage. If a card 's HP is a and its damage is b , then the power of the card is a x b . Each prop has only one attribute: power. In addition to vertex 1 and vertex n , there are some vertices that trigger special events. The special events are: When you get to vertex n , you can choose at most one of your cards and multiply its damage by 10^9 . The final boss is very strong, so you want to maximize the sum of the power of all your cards and props. Find the maximum possible sum of power of all your cards and props if you play the game optimally. The first line contains two integers n and m ( 2 <= q n <= q 200 , n - 1 <= q m <= q min( frac{n(n-1)}2, 2000) ) -- the number of the vertices and the number of the edges. In the following n lines, the i -th (1 <= q i <= q n) line describes the special event that will trigger on vertex i : In the following m lines, each line contains two integers u and v ( 1 <= q u < v <= q n ) representing a directed edge from vertex u to vertex v . It is guaranteed that every edge (u,v) appears at most once. It is guaranteed that there are no special events on vertex 1 and vertex n . It is guaranteed that for all i , there exists a path from vertex 1 to vertex n that passes through vertex i . Output a single integer -- the maximum sum of the power of all your cards and props. In the first example, we will play the game in the following order: In the end, we will have a card with (2+8)=10 H'...