Max Energy Grazing

Bessie the cow gets to graze in one of Farmer John's best fields on her birthday. The field has N patches of grass labeled from \(1\) to \(N\), each with a unique quality value. If Bessie eats the grass at a patch with quality \(Q\), she gains \(Q\) energy units.

The patches are connected by bi-directional paths. Moving from one patch to an adjacent patch costs \(E\) energy units. Bessie can choose any patch to start grazing and she may traverse through patches without eating the grass. However, once she eats grass of a certain quality, she will never eat grass of that quality or lower in the future. She may pass by high‐quality patches without eating and return later if it is beneficial.

Your task is to determine the maximum net energy Bessie can accumulate. The net energy is defined as the sum of the energy obtained from eating minus the energy spent moving along the paths.

Hint: Since Bessie can only eat in strictly increasing order of quality, one strategy is to consider the patches in order of increasing quality. For every patch, you can compute the minimum number of steps (each costing \(E\) units) needed to reach every other patch, and update a dynamic programming state representing the maximum energy that can be achieved when the last eaten patch is a particular node.

The formula for updating is: \( dp[v] = \max(dp[v], dp[u] + Q_v - E \times d(u,v)) \) for every patch \(u\) and \(v\) with \(Q_u < Q_v\) and where \(d(u,v)\) is the minimum number of steps between \(u\) and \(v\).

inputFormat

The first line contains two integers \(N\) and \(E\) (\(1 \le N \le 1000\) and \(1 \le E \le 1,000,000\)), representing the number of patches and the energy cost per move.

The second line contains \(N\) space-separated integers \(Q_1, Q_2, ... , Q_N\) representing the quality of the grass on each patch. All qualities are distinct.

The third line contains an integer \(M\) representing the number of bi-directional paths.

Each of the next \(M\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le N\)), indicating that there is a path between patch \(u\) and patch \(v\>.

outputFormat

Output a single integer, the maximum net energy Bessie can accumulate.

sample

3 1
5 10 20
2
1 2
2 3

33