You are given a tree T with n vertices (numbered 1 through n) and a letter in each vertex. The tree is rooted at vertex 1.

Let's look at the subtree Tv of some vertex v. It is possible to read a string along each simple path starting at v and ending at some vertex in Tv (possibly v itself). Let's denote the number of distinct strings which can be read this way as <image>. 

Also, there's a number cv assigned to each vertex v. We are interested in vertices with the maximum value of <image>.

You should compute two statistics: the maximum value of <image> and the number of vertices v with the maximum <image>.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 300 000) — the number of vertices of the tree.

The second line contains n space-separated integers ci (0 ≤ ci ≤ 109).

The third line contains a string s consisting of n lowercase English letters — the i-th character of this string is the letter in vertex i.

The following n - 1 lines describe the tree T. Each of them contains two space-separated integers u and v (1 ≤ u, v ≤ n) indicating an edge between vertices u and v.

It's guaranteed that the input will describe a tree.

Output

Print two lines. 

On the first line, print <image> over all 1 ≤ i ≤ n. 

On the second line, print the number of vertices v for which <image>.

Examples

Input

10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3


Output

51
3


Input

6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6


Output

6
2

Note

In the first sample, the tree looks like this:

<image>

The sets of strings that can be read from individual vertices are:

<image>

Finally, the values of <image> are:

<image>

In the second sample, the values of <image> are (5, 4, 2, 1, 1, 1). The distinct strings read in T2 are <image>; note that <image> can be read down to vertices 3 or 4.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

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

    static class TaskD_Trie_CF {
        int[] am;
        int[] diff;
        List<Integer>[] g;
        char[] letterInVertex;
        int[] costPerVertex;
        int n;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            costPerVertex = Utils.readIntArray(in, n);
            letterInVertex = in.nextString().toCharArray();
            g = new List[n];
            for (int i = 0; i < n; ++i) {
                g[i] = new ArrayList<Integer>();
            }
            for (int i = 0; i < n - 1; ++i) {
                int a = in.nextInt() - 1;
                int b = in.nextInt() - 1;
                g[a].add(b);
                g[b].add(a);
            }

            am = new int[n];
            diff = new int[n];

            dfs1(0, -1);
            go(0, -1);

            int res = -1, count = 0;
            for (int i = 0; i < n; ++i) {
                if (res < costPerVertex[i] + diff[i]) {
                    res = costPerVertex[i] + diff[i];
                    count = 1;
                } else if (res == costPerVertex[i] + diff[i]) {
                    ++count;
                }
            }
//        System.err.println(ArrayUtils.toString(diff));
            out.println(res);
            out.println(count);
        }

        int dfs1(int v, int p) {
            for (int u : g[v]) if (u != p) am[v] += dfs1(u, v);
            return ++am[v];
        }

        TrieNode go(int v, int p) {
            int heavyV = -1;
            for (int u : g[v])
                if (u != p) {
                    if (heavyV == -1 || am[heavyV] < am[u]) {
                        heavyV = u;
                    }
                }
            if (heavyV == -1) {
                // That is leaf then.
                TrieNode root = new TrieNode();
                diff[v] = 1;
                addChar(root, letterInVertex[v], new TrieNode());
                return root;
            }

            TrieNode curRoot = go(heavyV, v);
            TrieNode root = new TrieNode();
            diff[v] = diff[heavyV] + 1;
            addChar(root, letterInVertex[v], curRoot);

            for (int u : g[v])
                if (u != p && u != heavyV) {
                    diff[v] += dfs(root.next[letterInVertex[v] - 'a'], u, v);
                }
            for (int u : g[v])
                if (u != p && u != heavyV) {
                    go(u, v);
                }

            return root;
        }

        private int dfs(TrieNode root, int v, int p) {
            int curLetter = letterInVertex[v] - 'a';
            int res = 0;
            if (root.next[curLetter] == null) {
                ++res;
                TrieNode newNode = new TrieNode();
                addChar(root, letterInVertex[v], newNode);
            }
            TrieNode t = root.next[curLetter];
            for (int u : g[v])
                if (u != p) {
                    res += dfs(t, u, v);
                }
            return res;
        }

        private void addChar(TrieNode root, char c, TrieNode newNode) {
            root.next[c - 'a'] = newNode;
        }

        class TrieNode {
            TrieNode[] next;

            public TrieNode() {
                next = new TrieNode[26];
            }

        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }

    static class Utils {
        public static int[] readIntArray(InputReader in, int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }
            return a;
        }

    }
}

