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.*;
import java.util.*;

public class Task {

    public static void main(String[] args) throws Exception {

        new Task().go();
    }

    PrintWriter out;
    Reader in;
    BufferedReader br;

    Task() throws IOException {

        try {

            //br = new BufferedReader( new FileReader("input.txt") );
            //in = new Reader("input.txt");
            in = new Reader("input.txt");
            out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        }
        catch (Exception e) {

            //br = new BufferedReader( new InputStreamReader( System.in ) );
            in = new Reader();
            out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );
        }
    }

    void go() throws Exception {

        //int t = in.nextInt();
        int t = 1;
        while (t > 0) {
            solve();
            t--;
        }

        out.flush();
        out.close();
    }


    int inf = 2000000000;
    int mod = 1000000007;
    double eps = 0.000000001;

    int n;
    int m;

    ArrayList<Integer>[] g;
    int[] a;

    void solve() throws IOException {

        int n = in.nextInt();
        g = new ArrayList[n];
        a = new int[n];

        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
            a[i] = in.nextInt();
        }

        for (int i = 0; i < n - 1; i++) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            g[x].add(y);
            g[y].add(x);
        }

        dfs(0, -1);
        countMax(0, -1);

//        for (int i = 0; i < n; i++)
//            if (!used[i]) {
//                tmax = Long.MIN_VALUE;
//                countMax(i, -1);
//                if (tmax == max)
//                    cnt++;
//            }


        //System.err.println(c);
        //System.err.println(max);

        out.println(max * c + " " + c);
    }

    long max = Long.MIN_VALUE;
    long tmax = Long.MIN_VALUE;

    int c = 0;

    long dfs(int v, int p) {

        long sum = a[v];

        for (int u : g[v])
            if (u != p) {
                long res = dfs(u, v);
                if (res > 0) {
                    sum += res;
                }
          }

        max = Math.max(sum, max);
        return sum;
    }

    long countMax(int v, int p) {

        long sum = a[v];
        for (int u : g[v])
            if (u != p) {
                long res = countMax(u, v);
                if (res > 0 && res != max)
                    sum += res;
            }

        if (sum == max)
            c++;

        return sum;
    }

    class Pair implements Comparable<Pair>{

        int a;
        int b;

        Pair(int a, int b) {

            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p) {

            if (a > p.a) return 1;
            if (a < p.a) return -1;
            if (b > p.b) return 1;
            if (b < p.b) return -1;
            return 0;
        }
    }

    class Item {

        int a;
        int b;
        int c;

        Item(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }


    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }


        String nextLine() throws IOException {
            return br.readLine();
        }

    }

    static class InputReader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public InputReader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public InputReader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

} 