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.*;

public class aoc {
  private static InputReader in;
  private static PrintWriter out;
  public static ArrayList<Integer>[] graph;
  public static long[] count;
  public static long[] rr;
  public static char[] c;
  public static int[][] tr;

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);
    int n = in.nextInt();
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) arr[i] = in.nextInt();
    c = in.next().toCharArray();
    graph = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int i = 0; i < n-1; i++) {
        int a = in.nextInt()-1, b = in.nextInt()-1;
        graph[a].add(b);
        graph[b].add(a);
    }
    tr = new int[n][26];
    count = new long[n];
    rr = new long[n];
    for (int i = 0; i < n; i++) Arrays.fill(tr[i], -1);
    dfs(0, -1);
    
    long mx = 0;
    for (int i = 0; i < n; i++) {
        if (rr[i] + arr[i] > mx) {
            mx = rr[i] + arr[i];
        }
    }
    int ct = 0;
    for (int i = 0; i < n; i++) {
        if (rr[i] + arr[i] == mx) {
            ct++;
        }
    }
    out.println(mx);
    out.println(ct);
    
    out.close();
    System.exit(0);
  }
  
  public static void dfs(int node, int par) {
      for (int next : graph[node]) {
          if (next == par) continue;
          dfs(next, node);
          
          int label = c[next]-'a';
          if (tr[node][label] == -1) {
              tr[node][label] = next;
          } else {
              merge(tr[node][label], next);
          }
      }
      ensureCount(node);
      rr[node] = count[node];
  }
  
  public static void merge(int a, int b) {
      for (int j = 0; j < 26; j++) if (tr[b][j] != -1) {
          if (tr[a][j] == -1) {
              tr[a][j] = tr[b][j];
          } else {
              merge(tr[a][j], tr[b][j]);
          }
      }
      ensureCount(a);
  }
  
  public static void ensureCount(int node) {
      count[node] = 1;
      for (int j = 0; j < 26; j++) {
          if (tr[node][j] != -1) {
              count[node] += count[tr[node][j]];
          }
      } 
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

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