For any given DAG $G=(V, E)$ and a starting vertex $s_1 \in V$ in the graph, the rules of the "Multiplication Game" are as follows:

• In the $i$-th round of operations ($i=1, 2, \dots$), the player chooses a non-empty path $p_i$ starting at $s_i$ such that the sum of the edge weights of all edges in this path is a multiple of $(i+1)$. If no such path can be chosen, the game is considered a failure, and the player receives no score. Otherwise, the operation is successful, and the endpoint of $p_i$ is denoted as $s_{i+1}$.
• After a successful $i$-th round, the player can choose to end the game or continue to the $(i+1)$-th round. If the player chooses to end the game, the chosen $i$ paths $p_1, \dots, p_i$ are called "multiplication paths," and the score is calculated.

If the game does not fail, for the chosen multiplication paths $p_1, \dots, p_k$, the score of the game is defined as $\sum_{i=1}^k a_i |p_i| / k$, where $|p_i|$ denotes the number of edges in path $p_i$, and $a_i$ are given weights. Obviously, no matter how the paths are chosen, at most $(n-1)$ paths can be selected, so the input only provides $a_1, \dots, a_{n-1}$.

To set the clearance requirements for each graph, please calculate the maximum score of the game for the given DAG and starting vertex.

Input

The first line contains three space-separated positive integers $n$, $m$, and $s_1$, representing the number of vertices, the number of edges, and the index of the starting vertex, respectively. It is guaranteed that $2 \le n \le 100$, $1 \le m \le \frac{n(n-1)}{2}$, and $1 \le s_1 \le n$.

The second line contains $(n-1)$ space-separated positive integers $a_1, \dots, a_{n-1}$, representing the weights used for score calculation. It is guaranteed that $1 \le a_1 \le a_2 \le \dots \le a_{n-1} \le 10^9$.

The next $m$ lines each contain three space-separated positive integers $u_i, v_i, w_i$, describing a directed edge from $u_i$ to $v_i$ with weight $w_i$. It is guaranteed that $1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$, the graph is connected, and there are no multiple edges.

Output

Output a single line containing two integers separated by a space.

If at least one path can be chosen, there exists an optimal selection scheme that maximizes the score. Let the simplest fractional representation of this optimal score be $p/q$ (if the optimal score is an integer, $q=1$). Output $p$ and $q$. Otherwise, if it is impossible to choose at least one path, output -1 -1.

Examples

Input 1

5 5 1
1 11 21 1211
1 2 4
1 3 11
2 5 9
3 4 12
4 5 13

Output 1

6 1

Note 1

The chosen multiplication paths are $p_1 = ((1, 2)), p_2 = ((2, 5))$.

Input 2

9 16 1
1 10 100 1000 10000 100000 1000000 10000000
1 2 2
1 3 3
2 3 5
2 5 7
3 4 11
3 5 13
3 6 17
3 7 19
4 7 23
5 6 29
5 8 31
6 7 37
6 8 41
6 9 43
7 9 47
8 9 53

Output 2

221 3

Subtasks

For $100\%$ of the data, it is guaranteed that $2 \le n \le 100$, $1 \le m \le \frac{n(n-1)}{2}$, $1 \le s_1, u_i, v_i \le n$, $1 \le a_1 \le \dots \le a_{n-1} \le 10^9$, $1 \le w_i \le 10^9$, the input graph is connected, and there are no multiple edges.