Problem: On the way home, Karen decided to stop by the supermarket to buy some groceries.

<image>

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.

The supermarket sells n goods. The i-th good can be bought for ci dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by di. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all i ≥ 2, in order to use the i-th coupon, Karen must also use the xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?

Input

The first line of input contains two integers n and b (1 ≤ n ≤ 5000, 1 ≤ b ≤ 109), the number of goods in the store and the amount of money Karen has, respectively.

The next n lines describe the items. Specifically:

  * The i-th line among these starts with two integers, ci and di (1 ≤ di < ci ≤ 109), the price of the i-th good and the discount when using the coupon for the i-th good, respectively. 
  * If i ≥ 2, this is followed by another integer, xi (1 ≤ xi < i), denoting that the xi-th coupon must also be used before this coupon can be used. 

Output

Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.

Examples

Input

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5


Output

4


Input

5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4


Output

5

Note

In the first test case, Karen can purchase the following 4 items:

  * Use the first coupon to buy the first item for 10 - 9 = 1 dollar. 
  * Use the third coupon to buy the third item for 12 - 2 = 10 dollars. 
  * Use the fourth coupon to buy the fourth item for 20 - 18 = 2 dollars. 
  * Buy the sixth item for 2 dollars. 



The total cost of these goods is 15, which falls within her budget. Note, for example, that she cannot use the coupon on the sixth item, because then she should have also used the fifth coupon to buy the fifth item, which she did not do here.

In the second test case, Karen has enough money to use all the coupons and purchase everything.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CKarenAndSupermarket solver = new CKarenAndSupermarket();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CKarenAndSupermarket {
        long inf = (long) 1e18;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int b = in.readInt();

            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
                nodes[i].c = in.readInt();
                nodes[i].d = in.readInt();

                if (i > 0) {
                    Node p = nodes[in.readInt() - 1];
                    p.adj.add(nodes[i]);
                }
            }


            dfsForSize(nodes[0]);
            dfs(nodes[0]);

            int ans = 0;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j <= n; j++) {
                    if (nodes[0].dp[i][j] <= b) {
                        ans = Math.max(ans, j);
                    }
                }
            }

            out.println(ans);
        }

        public void dfsForSize(Node root) {
            root.size = 1;
            for (Node node : root.adj) {
                dfsForSize(node);
                root.size += node.size;
            }
        }

        public void dfs(Node root) {
            root.dp = new long[2][root.size + 1];
            SequenceUtils.deepFill(root.dp, inf);
            root.dp[0][0] = 0;
            root.dp[0][1] = root.c;
            root.dp[1][1] = root.c - root.d;
            int curSize = 1;

            for (Node node : root.adj) {
                dfs(node);
                for (int i = node.size + curSize; i >= 0; i--) {
                    //i - j <= node.size
                    //j >= i - node.size
                    long dp0 = inf;
                    long dp1 = inf;
                    for (int j = Math.max(0, i - node.size); j <= curSize && j <= i; j++) {
                        int k = i - j;
                        //for zero
                        dp0 = Math.min(dp0, node.dp[0][k] + root.dp[0][j]);
                        dp1 = Math.min(dp1, Math.min(node.dp[1][k], node.dp[0][k]) + root.dp[1][j]);
                    }
                    root.dp[0][i] = dp0;
                    root.dp[1][i] = dp1;
                }

                curSize += node.size;
            }

            return;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class Node {
        List<Node> adj = new ArrayList<>();
        int c;
        int d;
        int size;
        long[][] dp;
        int id;

        public String toString() {
            return "" + id;
        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, long val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof long[]) {
                long[] longArray = (long[]) array;
                Arrays.fill(longArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }
}