Problem: You've got a weighted tree, consisting of n vertices. Each edge has a non-negative weight. The length of the path between any two vertices of the tree is the number of edges in the path. The weight of the path is the total weight of all edges it contains. 

Two vertices are close if there exists a path of length at most l between them and a path of weight at most w between them. Count the number of pairs of vertices v, u (v < u), such that vertices v and u are close.

Input

The first line contains three integers n, l and w (1 ≤ n ≤ 105, 1 ≤ l ≤ n, 0 ≤ w ≤ 109). The next n - 1 lines contain the descriptions of the tree edges. The i-th line contains two integers pi, wi (1 ≤ pi < (i + 1), 0 ≤ wi ≤ 104), that mean that the i-th edge connects vertex (i + 1) and pi and has weight wi.

Consider the tree vertices indexed from 1 to n in some way.

Output

Print a single integer — the number of close pairs.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

4 4 6
1 3
1 4
1 3


Output

4


Input

6 2 17
1 3
2 5
2 13
1 6
5 9


Output

9

Solution (in JAVA):

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

public class Z_E {
//    private FastScanner in;
//    private PrintWriter out;
    private int n, l, w, logn, number, numComp;
    private long ans;
    private int[] sizeSubtree, depth, weight, vertex, component;
    private List<Edge>[] edges;

    private void solve() throws IOException {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        l = in.nextInt();
        w = in.nextInt();
        inisialisation(n);

        for (int i = 1; i < n; i++) {
            int v = in.nextInt() - 1;
            int weight = in.nextInt();
            Edge e1 = new Edge(i, v, weight);
            Edge e2 = new Edge(v, i, weight);
            e1.rel = e2;
            e2.rel = e1;
            edges[i].add(e1);
            edges[v].add(e2);
        }

        //setSize(0, -1);
        calculate(0);

        ans = ans >> 1;
        System.out.println(ans + "");
    }

    class BIT {

        int[] arrBIT;

        BIT(int size) {
            arrBIT = new int[size];
        }

        BIT(int[] a) {
            arrBIT = new int[a.length];
            init(a);
        }

        /**
         * Range Sum query from 0 to right
         */
        int rsq(int right) {
            if (right < 0) return 0;
            if (right >= arrBIT.length) right = arrBIT.length - 1;
            int sum = 0;

            while (right >= 0) {
                sum += arrBIT[right];
                right = (right & (right + 1)) - 1;
            }

            return sum;
        }

        /**
         * Range Sum Query from a to b
         */
        int rsq(int left, int right) {
            return rsq(right) - rsq(left - 1);
        }


        /**
         * Update the array at ind
         */
        void update(int ind, int value) {
            while (ind < arrBIT.length) {
                arrBIT[ind] += value;
                ind |= ind + 1;
            }
        }

        /**
         * Ititialization Fenwick Tree with start array a
         */
        void init(int[] a) {
            for (int i = 0; i < arrBIT.length; ++i) {
                arrBIT[i] += a[i];
                if ((i | (i + 1)) < arrBIT.length) arrBIT[i | (i + 1)] += arrBIT[i];
            }
        }
    }

    class Edge {
        int from;
        int to;
        int w;
        Edge rel;
        boolean deleted;

        Edge(int from, int to, int w) {
            this.from = from;
            this.to = to;
            this.w = w;
        }
    }

    void delete(Edge e) {
        e.deleted = true;
        e.rel.deleted = true;
    }


    private void calculate(int v) {
        number = 0;
        setSize(v, -1);
        int root = findCentroid(v, -1, sizeSubtree[v], 0);
        setSize(root, -1);

        setValues(root, -1, 0, 0);

        int countChildren = 0;
        for (int i = 0; i < edges[root].size(); i++) {
            Edge e = edges[root].get(i);
            if (e.deleted) {
                continue;
            }
            countChildren++;
        }
        int[] children = new int[countChildren];
        countChildren = 0;
        for (int i = 0; i < edges[root].size(); i++) {
            Edge e = edges[root].get(i);
            if (e.deleted) {
                continue;
            }
            children[countChildren++] = e.to;
        }

        numComp = 0;
        component[root] = numComp++;
        for (Edge e : edges[root]) {
            if (e.deleted) continue;
            setComp(e.to, root, numComp++);
        }

        BIT tree = new BIT(sizeSubtree[root] + 1);
        BIT[] bit = new BIT[countChildren + 1];
        //int num = 0;
        bit[0] = new BIT(2);
        for (int i = 0; i < countChildren; i++) {
            bit[i + 1] = new BIT(sizeSubtree[children[i]] + 1);
        }
//        for (Edge e : edges[root]) {
//            if (e.deleted) continue;
//            bit[num++] = new BIT(sizeSubtree[e.to] + 1);
//        }

        Integer[] id = new Integer[number];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
//        Arrays.sort(id, new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return Integer.compare(weight[vertex[o1]], weight[vertex[o2]]);
//            }
//        });
        Arrays.sort(id, (Integer o1, Integer o2)-> Integer.compare(weight[vertex[o1]], (weight[vertex[o2]])));

        int curQ = number - 1;
        for (int i : id) {
            int cv = vertex[i];
            int cw = weight[cv];
            while (curQ >= 0) {
                int cu = vertex[id[curQ]];
                int cuw = weight[cu];
                if (cuw + cw > w) {
                    ans += tree.rsq(l - depth[cu]);
                    ans -= bit[component[cu]].rsq(l - depth[cu]);
                    curQ--;
                } else break;
            }

            tree.update(depth[cv], 1);
            bit[component[cv]].update(depth[cv], 1);
        }

        for (; curQ >= 0; curQ--) {
            int cv = vertex[id[curQ]];
            ans += tree.rsq(l - depth[cv]);
            ans -= bit[component[cv]].rsq(l - depth[cv]);
        }

//        for (Edge e : edges[root]) {
//            if (e.deleted) continue;
//            delete(e);
//            calculate(e.to);
//        }
        for (int i = 0; i < edges[root].size(); i++) {
            delete(edges[root].get(i));
        }
        for (int i : children) {
            calculate(i);
        }
    }


    private int findCentroid(int v, int parent, int size, int uptree) {
        for (Edge e : edges[v]) {
            if (e.to == parent || e.deleted) continue;
            if (sizeSubtree[e.to] > size / 2) {
                return findCentroid(e.to, v, size, uptree + sizeSubtree[v] - sizeSubtree[e.to]);
            }
        }
//        if (parent != -1)
//            sizeSubtree[parent] = uptree; // now v is root
        return v;
    }

    private void setComp(int v, int parent, int comp) {
        component[v] = comp;

        for (Edge e : edges[v]) {
            if (e.to == parent || e.deleted) continue;
            setComp(e.to, v, comp);
        }
    }

    private void setSize(int v, int parent) {
        sizeSubtree[v] = 1;

        for (Edge e : edges[v]) {
            if (e.to == parent || e.deleted) continue;
            setSize(e.to, v);
            sizeSubtree[v] += sizeSubtree[e.to];
        }
    }

    private void setValues(int v, int parent, int w, int d) {
        weight[v] = w;
        depth[v] = d;
        vertex[number++] = v;

        for (Edge e : edges[v]) {
            if (e.to == parent || e.deleted) continue;
            setValues(e.to, v, w + e.w, d + 1);
        }
    }

//    private int decBuild(int v, int size) {
//        int root = findCentroid(v, -1, size, 0);
//        deleted[root] = true;
//
//        for (Edge e: edges[root]) {
//            if (e.deleted) continue;
//            int subRoot = decBuild(e.to, sizeSubtree[e.to]);
//            parent[subRoot] = root;
//        }
//
//        return root;
//    }
//
//    private void buildTree(int v, int size) {
//        setSize(0, -1);
//        int root = decBuild(0, n);
//        parent[root] = -1;
//    }

    private void inisialisation(int size) {
        number = 0;
        ans = 0;
        weight = new int[size];
        depth = new int[size];
        vertex = new int[size];
        component = new int[size];
        edges = new List[size];
        sizeSubtree = new int[size];
        logn = (int) (Math.log(size) / Math.log(2)) + 1;

        for (int i = 0; i < size; i++) {
            edges[i] = new ArrayList<>();
        }
    }

    private void run() {
        try {
            //in = new FastScanner(new File("input.txt"));
            //out = new PrintWriter(new File("output.txt"));

            solve();
            //out.close();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        char nextChar() {
            try {
                return (char) br.read();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return 0;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        void nextLine() {
            try {
                br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    public static void main(String[] arg) {
        new Z_E().run();
    }
}