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.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.util.Comparator;
import java.io.InputStream;

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

  static class TaskD {
    private static final int CHARACTER_SIZE = 26;
    private int n;
    private int max;
    private int maxCount;
    private int[] weight;
    private char[] s;
    private int[][] c;
    private int[] dp;
    private int[] stack;
    private int[][] queue;
    private int[] label;
    private int[] size;
    private Graph graph;
    private int cn;
    private int top;
    private OutputWriter out;

    @SuppressWarnings("unchecked")
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      this.out = out;
      n = in.nextInt();
      weight = in.nextInts(n);
      s = in.nextChars();
      label = new int[n];
      size = new int[n];
      dp = new int[n];
      c = new int[n * 2 + 10][CHARACTER_SIZE];
      stack = new int[n * 2];
      queue = new int[n][];
      cn = top = 0;
      graph = new Graph(n);
      for (int i = 1; i < n; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        graph.addEdge(u, v);
        graph.addEdge(v, u);
      }
      max = maxCount = 0;
      dfs(0);
      out.println(max).println(maxCount);
    }

    private void dfs(int u) {
      int father = 0;
      size[u] = 1;
      for (int v : graph.adj(u)) {
        if (size[v] != 0) {
          father = v;
          continue;
        }
        dfs(v);
        size[u] += size[v];
      }
      if (size[u] == 1) {
        label[u] = newNode();
        c[label[u]][s[u] - 'a'] = newNode();
        dp[u] = 1;
        updateAnswer(dp[u] + weight[u]);
        return;
      }
      graph.sortEdges(u, (a, b) -> size[b] - size[a]);
      for (int v : graph.adj(u)) {
        if (v == father) continue;
        if (label[u] == 0) {
          label[u] = label[v];
          dp[u] = dp[v] + 1;
        } else {
          int f = 0, b = 0;
          queue[b++] = new int[]{label[u], label[v]};
          while (f != b) {
            int pu = queue[f][0], pv = queue[f][1];
            f++;
            for (int i = 0; i < CHARACTER_SIZE; i++) {
              if (c[pv][i] != 0) {
                if (c[pu][i] == 0) {
                  c[pu][i] = newNode();
                  dp[u]++;
                }
                queue[b++] = new int[]{c[pu][i], c[pv][i]};
              }
            }
          }
          for (int i = 0; i < b; i++) stack[top++] = queue[i][1];
        }
      }
      int newId = newNode();
      c[newId][s[u] - 'a'] = label[u];
      label[u] = newId;
      updateAnswer(dp[u] + weight[u]);
    }

    private void updateAnswer(int res) {
      if (res > max) {
        max = res;
        maxCount = 0;
      }
      if (res == max) maxCount++;
    }

    private int newNode() {
      if (top > 0) {
        Arrays.fill(c[stack[--top]], 0);
        return stack[top];
      } else {
        return ++cn;
      }
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    public String next() {
      if (hasNext()) return tokenizer.nextToken();
      else throw new NoSuchElementException();
    }

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

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

    public char[] nextChars() {
      return next().toCharArray();
    }

    public boolean hasNext() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String nextLine = reader.readLine();
          if (nextLine == null) return false;
          tokenizer = new StringTokenizer(nextLine);
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.hasMoreTokens();
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter println(int value) {
      writer.println(value);
      return this;
    }

    public void close() {
      writer.close();
    }

  }

  static class Graph {
    protected final List<Integer>[] edges;
    protected final int n;
    protected int m = 0;

    @SuppressWarnings("unchecked")
    public Graph(int n) {
      this.n = n;
      this.edges = new List[n];
      for (int i = 0; i < n; i++) {
        edges[i] = new ArrayList<>();
      }
    }

    public void addEdge(int u, int v) {
      edges[u].add(v);
      m++;
    }

    public int adjSize(int u) {
      return edges[u].size();
    }

    public void sortEdges(int u, Comparator<Integer> comparator) {
      edges[u].sort(comparator);
    }

    public Iterable<Integer> adj(int u) {
      return edges[u];
    }


    public String toString() {
      StringBuilder stringBuilder = new StringBuilder();
      stringBuilder.append("graph with ").append(n).append(" nodes ");
      int res = 0;
      for (int i = 0; i < n; i++) res += adjSize(i);
      stringBuilder.append(res / 2).append(" edges\n");
      for (int u = 0; u < n; u++) {
        for (int v : adj(u)) {
          if (u < v) {
            stringBuilder.append(u).append(" ").append(v).append("\n");
          }
        }
      }
      return stringBuilder.toString();
    }

  }
}

