Problem D
Let's Play Monopoly!

Monopoly is a fast-dealing property trading game, which is firstly designed by Elizabeth Magie and then published as well as owned by Hasbro. Since its first appearance in 1935, this game has quickly become well-known and deserves the best way of enjoying with friends at leisure. In this game, you can demonstrate your powerful investing skill and your great support from the God by throwing dices, travelling on a risky board and building your real estate for the purpose of forcing your opponents to pay huge amounts of money for renting your land, which eventually leads to bankruptcy. Various localized versions of Monopoly have been introduced, consisting of different famous places all over the world, while their layout share the same. The figure below shows the board of UK Edition Monopoly.

If you have enjoyed delightful moments with Monopoly, I wish you can entertain yourselves by solving this problem. Otherwise, do not worry as in this problem we are playing a significantly simplified version of this game. Forget the rules of the traditional game and read carefully the below description:

In this problem, instead of a board, the game is held in a graph with $N$ nodes and $M$ directed edges. Two players, Alob and Bice join the game. At the beginning, Alob is at node $s_a$ while Bice is at node $s_b$. Alob starts first. Two players take turn alternatively. In each turn, a player has to move from his current node, along some edge to another node; and may pay, collect money or buy property, depending on the type of the new node. If he can not choose any edges to pass through, he has to pass that turn (do nothing).

Every node belongs to one of the following types:

• Property: You can purchase to own this property and force your opponents to pay you when they reach here. Each property has its own buying cost and renting cost. Initially, all properties are unowned. When you reach an unowned property, you can decide either to buy this property (you have to pay its buying cost) to permanently own it, or to ignore. After you purchase for this property, your opponent has to send you an amount of money equal to its renting cost everytime he reaches it. Of course, you have nothing to do while landing on your own properties.

• Salary: Each node of this kind has its own value, which is the amount of money you gain everytime you reach this.

• Tax: Each node of this kind has its own value, which is the amount of money you lose when you reach this node.

Since Alob and Bice are bored of playing an overlong game, each person will take at most $K$ turns (including passed turns). After that, the game ends. They had already won the gameshow Who Wants to Be a Millionaire? so they never worry about running out of cash. Each player wants his money to be more than his opponent’s money as much as possible. If he has several strategies resulting in the same difference, he always prefers the one giving him largest amount of money.

Assume that both player play optimally, your task is to determine the outcome of the game.

Input

The first line contains five integers: $N$, $M$, $K$, $s_a$, $s_b$ - the number of nodes and edges in the graph, the maximum number of turns each player takes, and the starting nodes of Alob and Bice, respectively.

The $i^{th}$ line of the next $M$ lines contains two integers $u_i$ and $v_i$, representing an edge from $u_i$ to $v_i$.

The $i^{th}$ line of the last $N$ lines describes the $i^{th}$ node of the graph in one of the following formats:

• PROPERTY b r: Denotes that this node has a property with buying_cost $b$ and renting_cost $r$.

• SALARY v: Denotes that a player earns $v$ when entering this node.

• TAX v: Denotes that a player loses $v$ when entering this node.

Output

Write out in one line two space-separated integers denoting the amount of money Alob and Bice gain at the end of the game, respectively.

Constraints

• $1\le N\le {10}^5$

• $0\le M\le {10}^5$

• ${10}^6\le K\le {10}^9$

• $1\le s_a\le N$, $1\le s_b\le N$

• All other numbers in the input files are integers between $1$ and ${10}^9$, inclusive.

• For all nodes which has property, $renting\mathrm{\_}cost\le \frac{buying\mathrm{\_}cost}{\pi }$.

• For every $i$ from $1$ to $M$, $1\le u_i<v_i\le N$.

12 12 123456789 1 2
1 3
1 5
3 7
3 9
5 9
7 11
2 4
2 6
4 8
4 10
6 8
8 12
SALARY 1
SALARY 10000
TAX 3
TAX 200
SALARY 10
TAX 1000
SALARY 7
PROPERTY 50 14
TAX 18
PROPERTY 105 33
PROPERTY 11 2
SALARY 7

4 -193