The Great Cyrus
/

## Flow, Greedy algorithm

Problem
Editorial
Analytics

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 ai gold and bi 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 ai and bi for every city except s and t, in order of cities indices (1 ≤ ai, bi ≤ 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.

SAMPLE INPUT
4 3
1 4
10 30
10 40
1 2
3 2
4 3

SAMPLE OUTPUT
10 30

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...