Description

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

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 dollars.

The supermarket sells goods. The -th good can be bought for 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 coupons. If Karen purchases the -th good, she can use the -th coupon to decrease its price by . Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all , in order to use the -th coupon, Karen must also use the -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 ?

Input Format

The first line of input contains two integers nn and bb ( 1<=n<=50001<=n<=5000 , 1<=b<=10^{9}1<=b<=109 ), the number of goods in the store and the amount of money Karen has, respectively.

The next nn lines describe the items. Specifically:

• The ii -th line among these starts with two integers, c_{i}ci​ and d_{i}di​ ( 1<=d_{i}<c_{i}<=10^{9}1<=di​<ci​<=109 ), the price of the ii -th good and the discount when using the coupon for the ii -th good, respectively.
• If i>=2i>=2 , this is followed by another integer, x_{i}xi​ ( 1<=x_{i}<i1<=xi​<i ), denoting that the x_{i}xi​ -th coupon must also be used before this coupon can be used.

Output Format

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

Input / Output Samples

Input #1

1
2
3
4
5
6
7

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

Output #1

1

4

Input #2

1
2
3
4
5
6

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

Output #2

1

5

解析

从代码里复制过来的（

一道树形 DP

显然优惠券的使用逻辑可以构成一棵树
设 表示在树根为 i 的子树中购买 j 件商品，是(1)否(0)可以使用优惠券的最小花费
初始状态：

转移方程：

其中 ，i 需要倒序枚举来避免重复选商品

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//
//  CF816E.cpp
//  Title: Karen and Supermarket
//  Alternatives: CF815C
//  Debugging
//
//  Created by HandwerSTD on 2019/7/30.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }
// CodeForces 中请使用 %I64d

/**
 *
 * 显然优惠券的使用逻辑可以构成一棵树
 * 设 f[i][j][0/1] 表示在树根为 i 的子树中购买 j 件商品，是(1)否(0)可以使用优惠券的最小花费
 * 初始状态：
 * f[][][] = INF
 * f[i][1][0] = Read, f[i][1][1] = f[i][1][0] - Read
 * 转移方程：
 * f[root][i + j][0] = min{ f[root][i + j][0], f[root][i][0] + f[u][j][0] | u 为 root 的孩子 }
 * f[root][i + j][1] = min{ f[root][i + j][1], f[root][i][1] + min{ f[u][j][0], f[u][j][1] } | u 为 root 的孩子 }
 * 其中 i <= size[root], j <= size[u]，i 需要倒序枚举
 *
 */

const int MAXN = 5000 + 10;

int n, b;
std::vector<int> head[MAXN];
lli dp[MAXN][MAXN][2];
int size[MAXN];
// dp 数组耗空间约 383MB
// size 数组耗空间约 20KB

void DFS(int u = 1, int fa = 0) {
    size[u] = 1;
    for (int v : head[u]) {
        DFS(v, u);
        for (int i = size[u]; i >= 0; --i) {
            for (int j = 0; j <= size[v]; ++j) {
                dp[u][i + j][0] = std::min(
                    dp[u][i + j][0],
                    dp[u][i][0] + dp[v][j][0]
                );
                dp[u][i + j][1] = std::min(
                    dp[u][i + j][1],
                    dp[u][i][1] + std::min(
                        dp[v][j][0],
                        dp[v][j][1]
                    )
                );
            }
        }
        size[u] += size[v];
    }
}

int main() {
    n = getint(); b = getint();
    memset(dp, 0x7f, sizeof dp);
    rap (i, 1, n, 1) {
        dp[i][0][0] = 0;
        dp[i][1][0] = getll();
        dp[i][1][1] = dp[i][1][0] - getll();
        if (i >= 2) {
            int next = getint();
            head[next].push_back(i);
        }
    }
    DFS();
    int i = n;
    for (; i >= 1; --i) {
        if (dp[1][i][0] <= b || dp[1][i][1] <= b) break;
    }
    printf("%d\n", i);
    return 0;
}