For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exists ~N~ types of flowers. Each type of flower first multiplies the beauty of the bouquet by ~m_i~ and then increases its beauty by ~p_i~. Having two flowers of type ~i~ does not apply the effect of flower ~i~ twice. The initial beauty of the bouquet is ~0~ and flowers can be added in any order.
Some flowers do not go together. There are ~M~ such pairs where flowers ~a_i~ and ~b_i~ can not be in the same bouquet.
Because Evan will be receiving so many flowers, the size of your bouquet is limited to ~3~ flowers.
You would like to stand out by maximizing the beauty of your flower bouquet.
Note: Python users are recommended to use PyPy.
~1 \leq N, M, a_i, b_i \leq 300~
~0 \leq m_i, p_i \leq 1000~
~a_i \neq b_i~
The first line of input will contain integers ~N~ and ~M~.
The next ~N~ lines contain integers ~m_i,~ ~p_i~.
The next ~M~ lines contain integers ~a_i,~ ~b_i~.
Print one number, the maximum beauty of your bouquet.
Sample Input 1
4 0 10 0 1 1 2 1 1 3
Sample Output 1
Flower ~4~ is chosen, giving a beauty value of ~3~. Then flower ~3~ is chosen to yield ~3 \times 2 + 1 = 7~. Finally, choose flower ~1~ to get ~7 \times 10 = 70~.
Sample Input 2
4 1 1 1 6 0 5 5 2 0 2 3
Sample Output 2
While choosing flowers ~3, 4, 2~ would give ~60~, flowers ~2~ and ~3~ can not be in the same bouquet.
Instead, choose ~1, 3, 4~ to get ~20~.