All Tracks Problem

The Great Cyrus
Tag(s):

Flow, Greedy algorithm, Hard

Problem
Editorial
Analytics

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 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?