Skiing Adventure

a180285 loves skiing. He arrives at a snowy mountain that has (m) ski tracks and (n) intersections (which are also scenic spots). Each scenic spot has an index (i) (where (1 \le i \le n)) and a height (h_i).

He can slide from spot (i) to spot (j) if and only if there is an edge between (i) and (j) and the height condition (h_i \ge h_j) holds.

Unlike other skiing enthusiasts, a180285 prefers to visit as many scenic spots as possible – and he wants to do so by sliding the minimum total distance. Moreover, he carries a magical time capsule pill that, when taken, instantly returns him to any previously visited spot (this teleportation does not count towards the sliding distance). The pill may be used consecutively, so he can jump back multiple steps in his journey.

Starting at scenic spot (1), he wonders: under the assumption that the time capsule has no cost, what is the minimum total sliding distance required to visit the maximum number of scenic spots? In other words, among all strategies that visit the maximum number of spots, choose one that minimizes the sliding distance. Your task is to compute two numbers: the minimal total sliding distance and the number of scenic spots visited.

inputFormat

The input consists of several lines:

The first line contains two integers (n) and (m), denoting the number of scenic spots and the number of ski tracks, respectively.

The second line contains (n) integers: (h_1, h_2, \ldots, h_n), where (h_i) represents the height of the (i)-th scenic spot.

Each of the following (m) lines contains two integers (u) and (v), indicating that there is a ski track connecting scenic spots (u) and (v). Note that a track exists between (u) and (v) but sliding is only allowed from a spot with greater or equal height to a spot with lower (or equal) height (i.e. sliding from (u) to (v) is allowed if and only if (h_u \ge h_v), and similarly for (v) to (u)).

outputFormat

Output two integers separated by a space: the minimal total sliding distance and the total number of scenic spots visited in the optimal strategy.

sample

1 0
5

0 1