Maximum Happiness in Dreamscapes

PF is trapped in a series of dreamscapes. There are n distinct scenes, numbered from \(1\) to \(n\). Each scene \(j\) has a happiness value \(a_j\). When a scene is visited for the first time, its happiness value is added to PF’s total happiness.

PF suffers from schizophrenia and at any given moment his mind dwells in two dreamscapes simultaneously. There is an additional restriction: the absolute difference between the scene numbers of these two dreams must never exceed \(l\).

The scenes are connected by m one‐way (directed) edges. The \(i\)th edge is from scene \(u_i\) to scene \(v_i\). It is guaranteed that every scene can eventually be reached.

Initially both dreams start at scene \(1\) (and the happiness from scene \(1\) is collected only once). PF will awaken when both dreams reach scene \(n\).

Movement rules are as follows:

• If at some step the two current scenes \(A\) and \(B\) of the dreams are both directly connected to a common scene \(C\) (i.e. there are edges \(A \to C\) and \(B \to C\)), then PF can move both dreams simultaneously to scene \(C\). In this case, if scene \(C\) has not been visited previously by either dream, its happiness is added only once.
• Otherwise, PF may move one dream at a time to a scene reachable by the corresponding directed edge. When a dream moves to a new scene (which has not been visited by either dream before) the scene’s happiness is added.

Your task is to plan the moves such that when both dreams eventually reach scene \(n\) the total collected happiness is maximized.

Note: A scene’s happiness value is collected at its first visit only, even if both dreams visit it (or visit it at different times).

inputFormat

The first line contains three integers: \(n\) \(m\) \(l\).

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) where \(a_j\) is the happiness value of scene \(j\).

Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) indicating a one‐way edge from scene \(u_i\) to scene \(v_i\).

It is guaranteed that every scene is reachable.

outputFormat

Output a single integer, the maximum possible total happiness PF can accumulate when both dreams reach scene \(n\).

sample

3 3 1
5 10 15
1 2
2 3
1 3

30