Problem Description

For any DAG $G=(V,E)$ and a starting vertex $s_1\in V$ in the graph, the rules of the doubling mini-game are as follows:

• In the $i$-th round of operation ($i=1,2,\cdots$), the player chooses a non-empty path $p_i$ starting from $s_i$, such that the sum of edge weights along this path is exactly a multiple of $(i+1)$. If it is impossible to choose a path that satisfies the multiple requirement, then the game is considered failed, and the player will receive no score. Otherwise, this round is successful, and the endpoint of $p_i$ is recorded as $s_{i+1}$.

• After the $i$-th round is successful, the player may choose to end the game or continue to the $(i+1)$-th round. If the player chooses to end the game, then the chosen $i$ paths $p_1, \cdots, p_i$ are called doubling paths, and the score is calculated.

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

To set the clearance requirement for each graph, given the DAG and the starting vertex, compute the maximum possible score of this game.

Input Format

The first line contains three positive integers $n$, $m$, $s_1$ separated by spaces, representing the number of vertices, the number of edges, and the index of the starting vertex. 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)$ positive integers $a_1, \cdots, a_{n-1}$ separated by spaces, representing the weights used when calculating the score. It is guaranteed that $1\le a_1\le a_2\le\cdots\le a_{n-1}\le 10^9$.

In the next $m$ lines, each line contains three positive integers $u_i, v_i, w_i$ separated by spaces, 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 Format

Output exactly one line containing two integers separated by a space.

If at least one path can be selected, then there exists an optimal selection that maximizes the score. Let the simplest fractional form of this optimal score be $p/q$ (if the optimal score is an integer, take $q=1$), and output $p$ and $q$. Otherwise, if it is impossible to select at least one path no matter what, output -1 -1.

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

6 1

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

221 3

Hint

[Sample 1 Explanation]

The selected doubling paths are $p_1 = ((1, 2)), p_2 = ((2, 5))$.

[Constraints]

For $100\%$ of the testdata, 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 \cdots\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.

Translated by ChatGPT 5