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

//java.is.awesome

public class R333qD {

	static int n;
	static int c[];
	static char s[];
	static ArrayList<Integer> g[];
	static int idx[][], tot[];
	static int max, ans;
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter w = new PrintWriter(System.out);

		n = in.nextInt();
		c = in.nextIntArray(n);
		s = in.readString().toCharArray();

		g = new ArrayList[n];
		for (int i = 0; i < n; i++)
			g[i] = new ArrayList<Integer>();
		
		for(int i = 1; i < n; i++){
			int u = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			g[u].add(v);
			g[v].add(u);
		}

		idx = new int[n][26];
		tot = new int[n];
		max = -1; ans = 0;
		dfs(0 , -1);
		
		w.println(max);
		w.println(ans);
		w.close();
	}
	
	public static void dfs(int curr, int prev){
		tot[curr] = 1;
		for(int next : g[curr]){
			if(next != prev){
				dfs(next, curr);
				if(idx[curr][s[next] - 'a'] == 0){
					idx[curr][s[next] - 'a'] = next;
					tot[curr] += tot[next];
				}
				else{
					tot[curr] -= tot [ idx[curr][s[next] - 'a'] ];
					merge(idx[curr][s[next] - 'a'], next);
					tot[curr] += tot [ idx[curr][s[next] - 'a'] ];
				}
			}
		}
		if(tot[curr] + c[curr] > max){
			max = tot[curr] + c[curr];
			ans = 0;
		}
		if(tot[curr] + c[curr] == max)
			ans++;
	}
	
	static void merge(int u, int v){
		tot[u] = 1;
		for(int i = 0; i < 26; i++){
			if(idx[v][i] > 0){
				if(idx[u][i] > 0)
					merge(idx[u][i] , idx[v][i]);
				else
					idx[u][i] = idx[v][i];
			}
			if(idx[u][i] > 0)
				tot[u] += tot[idx[u][i]];
		}
	}

	static class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

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

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

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

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

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

		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

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