Problem: You are given a weighted tree consisting of n vertices. Recall that a tree is a connected graph without cycles. Vertices u_i and v_i are connected by an edge with weight w_i.

You are given m queries. The i-th query is given as an integer q_i. In this query you need to calculate the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices in the tree and the number of queries.

Each of the next n - 1 lines describes an edge of the tree. Edge i is denoted by three integers u_i, v_i and w_i — the labels of vertices it connects (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) and the weight of the edge (1 ≤ w_i ≤ 2 ⋅ 10^5). It is guaranteed that the given edges form a tree.

The last line of the input contains m integers q_1, q_2, ..., q_m (1 ≤ q_i ≤ 2 ⋅ 10^5), where q_i is the maximum weight of an edge in the i-th query.

Output

Print m integers — the answers to the queries. The i-th value should be equal to the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Queries are numbered from 1 to m in the order of the input.

Examples

Input


7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1


Output


21 7 15 21 3 


Input


1 2
1 2


Output


0 0 


Input


3 3
1 2 1
2 3 2
1 3 2


Output


1 3 3 

Note

The picture shows the tree from the first example: <image>

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;


public class AlgorithmQ2{
static int[] findArray;
static long[] sumArray;
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        int nodeNumber = in.nextInt();
        int edgeNumber = nodeNumber - 1;
        int queryNumber = in.nextInt();


         Edge[] edgeArray = new Edge[edgeNumber];
        Query[] queryArray = new Query[queryNumber];

        for (int i = 0; i < edgeNumber; i++) {
            Edge edge = new Edge();
            edge.from = in.nextInt();
            edge.to = in.nextInt();
            edge.weight = in.nextLong();
            edgeArray[i] = edge;
        }

        for (int i = 0; i < queryNumber; i++) {
            Query query = new Query();
            query.id = i;
            query.value = in.nextInt();
            queryArray[i] = query;

        }

        Arrays.sort(edgeArray, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return (int) (o1.weight - o2.weight);
            }
        });
        Arrays.sort(queryArray, new Comparator<Query>() {
            @Override
            public int compare(Query o1, Query o2) {
                return o1.value - o2.value;
            }
        });
       sumArray = new long[nodeNumber + 1];
       findArray = new int[nodeNumber + 1];

        for (int i = 1; i <= nodeNumber; i++) {
            sumArray[i] = 1;
            findArray[i] = i;
        }

        int i = 0;
        for (int j = 0; j <queryNumber; j++) {
            if (j != 0) {
                queryArray[j].answer = queryArray[j - 1].answer;
            }
            else{
                queryArray[j].answer=0;
            }
            while (i < edgeNumber && edgeArray[i].weight <= queryArray[j].value
            ) {
                int f = edgeArray[i].from;
                int t = edgeArray[i].to;
                long add = sumArray[find(f)] * sumArray[find(t)];
                queryArray[j].answer = add+queryArray[j].answer;
                Union(f, t);
                i++;
            }
        }



        Arrays.sort(queryArray, new Comparator<Query>() {
            @Override
            public int compare(Query o1, Query o2) {
                return o1.id-o2.id;
            }
        });


        for ( i = 0; i <queryNumber ; i++) {
            System.out.print(queryArray[i].answer+" ");
        }

        out.close();
    }

  static  int find(int x){
       if(x==findArray[x]){
           return x;
       }
       else{
          findArray[x] = find(findArray[x]);
           return findArray[x];
       }
    }


    static void Union(int from,int to){
        from = find(from);
        to = find(to);
        findArray[to] = from;
        sumArray[from] += sumArray[to];
        sumArray[to] = sumArray[from];
    }


    static class Query{
        int id;
        long answer;
        int value;

    }


    static class Edge{
        long weight;
        int from;
        int to;
    }

    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}