Doubling Game on DAG

We are given a directed acyclic graph (DAG) \(G = (V,E)\) and a starting vertex \(s_1 \in V\). In the Doubling Game, the player performs a sequence of rounds following these rules:

1. In round \(i\) (\(i = 1, 2, \ldots\)), starting from vertex \(s_i\), the player must choose a nonempty path \(p_i\) such that the sum of the weights along the edges in \(p_i\) is a multiple of \(i+1\) (i.e. the total is divisible by \(i+1\)). If no such path exists from \(s_i\) then the game fails and the score is zero. Otherwise, if a valid path exists, let \(s_{i+1}\) be the endpoint of \(p_i\>.
2. After completing round \(i\), the player may either terminate the game or continue to round \(i+1\). If the game is terminated after \(k\) rounds, then the chosen paths \(p_1, p_2, \ldots, p_k\) form a doubling path and the final score is defined as \[ \frac{\displaystyle\sum_{i=1}^{k} a_i\,|p_i|}{k}, \] where \(|p_i|\) is the number of edges in \(p_i\) and \(a_i\) is a weight provided as input.

Note that, since any sequence of paths cannot have more than \(n-1\) rounds, the input provides exactly \(a_1, a_2, \ldots, a_{n-1}\). Given the DAG and the starting vertex, your task is to compute the maximum score the player can achieve by optimally selecting the rounds. All formulas are expressed in \(\LaTeX\) format.

inputFormat

The input begins with a single line containing three integers \(n\), \(m\), and \(s\), where \(n\) is the number of vertices, \(m\) is the number of edges, and \(s\) is the starting vertex \(s_1\).

Then follow \(m\) lines. Each of these lines contains three integers \(u\), \(v\) and \(w\) representing a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\). It is guaranteed that the graph is a DAG.

The last line contains \(n-1\) integers \(a_1, a_2, \ldots, a_{n-1}\), separated by spaces.

outputFormat

Output a single number — the maximum score that can be achieved. If no valid sequence of moves exists, output 0.

sample

3 3 1
1 2 1
2 3 1
1 3 2
2 3

4