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.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class CF333D {
	static int max = 0;
	static int maxc = 0;

	static class Tree {
		List<Tree> children;
		char c;
		int ci, vi;

		// PHASE 2 members
		Tree[] normChildren;
		int nodeCount = 1;

		public Tree(char c, int ci) {
			children = new ArrayList<>();
			normChildren = new Tree[26];
			this.c = c;
			this.ci = ci;
		}

		public void normalize() {
			for (Tree t : children) {
				t.normalize();
				if (normChildren[t.c - 'a'] == null) {
					normChildren[t.c - 'a'] = t;
				} else {
					if (normChildren[t.c - 'a'].nodeCount > t.nodeCount) {
						merge(normChildren[t.c - 'a'], t);
					} else {
						merge(t, normChildren[t.c - 'a']);
						normChildren[t.c - 'a'] = t;
					}
				}
			}
			for (int i = 0; i < 26; i++) {
				if (normChildren[i] != null)
					nodeCount += normChildren[i].nodeCount;
			}
			vi = nodeCount + ci;
			if (vi > max) {
				max = vi;
				maxc = 1;
			} else if (vi == max)
				maxc++;
		}

		public int merge(Tree t0, Tree t1) {
			int ret = 0;
			for (int i = 0; i < 26; i++) {
				if (t1.normChildren[i] != null && t0.normChildren[i] == null) {
					t0.normChildren[i] = new Tree((char) (i + 'a'), 0);
					ret++;
				}
				if (t1.normChildren[i] != null) {
					ret += merge(t0.normChildren[i], t1.normChildren[i]);
				}
			}
			t0.nodeCount += ret;
			return ret;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		int[] values = Arrays.stream(in.readLine().split(" "))
				.mapToInt(s -> Integer.parseInt(s)).toArray();
		char[] str = in.readLine().toCharArray();
		Tree[] tree = new Tree[n];
		ArrayList<Integer>[] tree2 = new ArrayList[n];
		for (int i = 0; i < n; i++)
			tree2[i] = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			tree[i] = new Tree(str[i], values[i]);
		}
		for (int i = 0; i < n - 1; i++) {
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(strtok.nextToken()) - 1;
			int b = Integer.parseInt(strtok.nextToken()) - 1;
			tree2[a].add(b);
			tree2[b].add(a);
		}
		{
			Queue<Integer> q = new ArrayDeque<>();
			q.add(0);
			q.add(-1);
			while (!q.isEmpty()) {
				int node = q.poll();
				int p = q.poll();
				for (int j : tree2[node]) {
					if (j != p) {
						tree[node].children.add(tree[j]);
						q.add(j);
						q.add(node);
					}
				}
			}
		}
		tree[0].normalize();
		System.out.println(max + "\n" + maxc);
	}
}
