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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        EEhabAndAComponentChoosingProblem solver = new EEhabAndAComponentChoosingProblem();
        solver.solve(1, in, out);
        out.close();
    }

    static class EEhabAndAComponentChoosingProblem {
        long[] dp;
        long[] dp2;
        List[] g;
        long max;
        int cnt = 0;
        int[] a;

        void dfs0(int u, int p) {
            dp[u] = a[u];
            for (int i = 0; i < g[u].size(); i++) {
                int v = (int) g[u].get(i);

                if (v != p) {
                    dfs0(v, u);

                    dp[u] += dp[v];
                }
            }

            if (dp[u] < 0) {
                dp[u] = 0;
            }

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

        void dfs1(int u, int p) {
            dp2[u] = a[u];
            for (int i = 0; i < g[u].size(); i++) {
                int v = (int) g[u].get(i);

                if (v != p) {
                    dfs1(v, u);

                    dp2[u] += dp2[v];
                }
            }

            if (dp2[u] < 0) {
                dp2[u] = 0;
            }

            if (dp2[u] == max) {
                cnt++;
                dp2[u] = 0;
            }
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            a = in.nextIntArray(n);

            g = new List[n];

            in.readUndirectedGraph(g, n, n - 1, 1);

            boolean allneg = true;

            long negmax = (int) -1e9 - 1;
            int nmc = 0;

            for (int i = 0; i < n; i++) {
                if (a[i] > 0) {
                    allneg = false;
                    break;
                }

                if (negmax < a[i]) {
                    negmax = a[i];
                    nmc = 1;
                } else if (negmax == a[i]) {
                    nmc++;
                }
            }

            if (allneg) {
                out.println((negmax * nmc) + " " + nmc);
                return;
            }

            dp = new long[n];
            dp2 = new long[n];

            dfs0(0, -1);

            dfs1(0, -1);

            out.println((max * cnt) + " " + cnt);

//        PriorityQueue<ver> vers = new PriorityQueue<>((v1, v2) -> v1.d - v2.d);
//
//        int[] deg = new int[n];
//
//        for (int i = 0; i < n; i++) {
//            deg[i] = g[i].size();
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (a[i] <= 0 && deg[i] == 1)
//                vers.add(new ver(i, deg[i]));
//        }
//
//        boolean[] rem = new boolean[n];
//
//        while (vers.size() > 0) {
//            ver cv = vers.poll();
//
//            if (deg[cv.u] != cv.d) {
//                continue;
//            }
//
//            rem[cv.u] = true;
//
//            for (int i = 0; i < g[cv.u].size(); i++) {
//                int v = (int) g[cv.u].get(i);
//
//                if (rem[v])
//                    continue;
//
//                deg[v]--;
//
//                if (deg[v] <= 1 && a[v] <= 0) {
//                    vers.add(new ver(v, deg[v]));
//                }
//            }
//        }
//
//        List[] ng = new List[n];
//
//        for (int i = 0; i < n; i++) {
//            ng[i] = new ArrayList();
//
//            if (rem[i])
//                continue;
//            for (int j = 0; j < g[i].size(); j++) {
//                int v = (int) g[i].get(j);
//
//                if (!rem[v]) {
//                    ng[i].add(v);
//                }
//            }
//        }
//
//        g = ng;
//
//        long sum = 0;
//        int ck = 0;
//
//        vis = new boolean[n];
//
//        List<Long> negs = new ArrayList<>();
//
//        for (int i = 0; i < n; i++) {
//            if (!vis[i]) {
//                csum = 0;
//                if (a[i] < 0) {
//                    dfs(i, g, false);
//                } else if (a[i] > 0) {
//                    dfs(i, g, true);
//                }
//
//                if (csum < 0) {
//                    //negs.add(csum);
//                } else {
//                    //sum += csum;
//                    //ck++;
//                    negs.add(csum);
//                }
//            }
//        }
//
//        negs.sort(Comparator.reverseOrder());
//
//        double ans = (double) sum / ck;
//
//        long fsum = negs.get(0);
//        int fk = 1;
//
////        for (int i = ck - 1, j = 0; i >= 1; i--, j++) {
////            long nsum = sum + negs.get(j);
////
////            if (((double) nsum / i) > ans) {
////                ans = nsum / i;
////                fsum = nsum;
////                fk = i;
////            }
////
////            sum = nsum;
////        }
//
//        for (int i = 1; i < negs.size(); i++) {
//            if (negs.get(i) == fsum) {
//                fk++;
//            } else {
//                break;
//            }
//        }
//
//
//        out.println((fsum * fk) + " " + fk);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; ++i) array[i] = nextInt();
            return array;
        }

        public void readUndirectedGraph(List[] g, int numOfVertices, int numOfEdges, int offset) {
            for (int i = 0; i < numOfVertices; i++) {
                g[i] = new ArrayList();
            }

            for (int i = 0; i < numOfEdges; i++) {
                int u = nextInt() - offset;
                int v = nextInt() - offset;

                g[u].add(v);
                g[v].add(u);
            }
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}

