You're given a tree consisting of n nodes. Every node u has a weight a_u. You want to choose an integer k (1 ≤ k ≤ n) and then choose k connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be s. You want to maximize:

$$$\frac{∑_{u ∈ s} a_u}{k}$$$

In other words, you want to maximize the sum of weights of nodes in s divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize k.

Note that adjacent nodes can belong to different components. Refer to the third sample.

Input

The first line contains the integer n (1 ≤ n ≤ 3 ⋅ 10^5), the number of nodes in the tree.

The second line contains n space-separated integers a_1, a_2, ..., a_n (|a_i| ≤ 10^9), the weights of the nodes.

The next n-1 lines, each contains 2 space-separated integers u and v (1 ≤ u,v ≤ n) which means there's an edge between u and v.

Output

Print the answer as a non-reduced fraction represented by 2 space-separated integers. The fraction itself should be maximized and if there are several possible ways, you should maximize the denominator. See the samples for a better understanding.

Examples

Input


3
1 2 3
1 2
1 3


Output


6 1

Input


1
-2


Output


-2 1

Input


3
-1 -1 -1
1 2
2 3


Output


-3 3

Input


3
-1 -2 -1
1 2
1 3


Output


-2 2

Note

A connected component is a set of nodes such that for any node in the set, you can reach all other nodes in the set passing only nodes in the set.

In the first sample, it's optimal to choose the whole tree.

In the second sample, you only have one choice (to choose node 1) because you can't choose 0 components.

In the third sample, notice that we could've, for example, chosen only node 1, or node 1 and node 3, or even the whole tree, and the fraction would've had the same value (-1), but we want to maximize k. 

In the fourth sample, we'll just choose nodes 1 and 3.
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    private static long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};
    private static final String yes = "Yes";
    private static final String no = "No";

    int n;
    int[][] graph;
    long[] arr;
    long max = Long.MIN_VALUE;
    long[] dp;
    int k = 0;
    int[] from;
    int[] to;
    void solve() throws IOException {
        n = nextInt();
        from = new int[n - 1];
        to = new int[n - 1];
        arr = nextLongArr(n);
        for (int i = 0; i < n - 1; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            from[i] = u;
            to[i] = v;
        }

        graph = packD(n, from, to, false);
        dp = new long[n];
        Arrays.fill(dp, Long.MIN_VALUE);
        dfs1(0, -1);
        dfs2(0, -1);
        outln(k * max + " " + k);
    }

    void dfs2(int cur, int parent) {
        long sum = arr[cur];
        for (int nxt : graph[cur]) {
            if (nxt == parent) {
                continue;
            }

            dfs2(nxt, cur);
            sum += Math.max(dp[nxt], 0);
        }

        if (max == sum) {
            k++;
            dp[cur] = 0;
        }
        else {
            dp[cur] = sum;
        }
    }

    void dfs1(int cur, int parent) {
        long sum = arr[cur];
        for (int nxt : graph[cur]) {
            if (nxt == parent) {
                continue;
            }

            dfs1(nxt, cur);
            sum += Math.max(dp[nxt], 0);
        }

        max = Math.max(max, sum);
        dp[cur] = sum;
    }

    // compress graph in a 2d array
    static int[][] packD(int n, int[] from, int[] to, boolean directed) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from) p[f]++;
        if (!directed) {
            for (int t : to) {
                p[t]++;
            }
        }

        for (int i = 0; i < n; i++) {
            g[i] = new int[p[i]];
        }

        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
        }

        if (!directed) {
            for (int i = 0; i < to.length; i++) {
                g[to[i]][--p[to[i]]] = from[i];
            }
        }

        return g;
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    private void formatPrint(double val) {
        outln(String.format("%.9f%n", val));
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}