For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exist ~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.

Constraints

~1 \le N, M, a_i, b_i \le 300~

~0 \le m_i, p_i \le 1000~

~a_i \ne b_i~

Input Specification

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~.

Output Specification

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

70

Explanation for 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

20

Explanation for 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~.