View Russian Translation

The great Cyrus is in a great war with his enemies.

His country has n cities and m bidirectional roads. Cities are numbered from 1 to n. The capital is city number s and his enemies are in city t. There is no direct road between s and t.

He wants to mobilize some cities (he can't mobilize s and t). Enemies can't pass mobilized cities. He wants to do this so that enemies won't be able to get to the capital crossing only unmobilized cities and using only country roads.

For each city i which is not s and t, Cyrus knows mobilizing city i costs a_i gold and b_i silver coins.

Gold is way too worthier than silver in his country, so in the first place he wants to minimize the total gold coins he spends. And among all possible solutions with minimum gold, he chooses the mobilizing way with minimum total silver coins.

Your task as Cyrus' minister is to chose this optimal solution and tell him how much gold and silver coins he needs.

Please note that there may be no path from t to s and so Cyrus needs no coins at all.

Input

The first line of input contains two integers n and m (3 ≤ n ≤ 500, 1 ≤ m ≤ n(n-1)/2 -1).

The second line contains two integers s and t (1 ≤ s, t ≤ n, s ≠ t).

The next n-2 lines, each line contains two integers a_i and b_i for every city except s and t, in order of cities indices (1 ≤ a_i, b_i ≤ 1000).

The next m lines contain the roads. Each line contains two integers v and u, endpoints of a road.

(1 ≤ v, u ≤ n, v ≠ u, there is at most 1 road between two cities and there'll be no road between s and t).

Output

Print two integers in a line, number of gold and silver coins needed in an optimal solution.