永不言弃

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K

Articles

小沙最喜欢打怪升级了，今天他玩了一个游戏，需要从初始关卡开始，击败 $n$ 个关卡才能通关整个游戏，对于每个关卡都会有两种通过方式。

小沙初始的属性值为 $s$ ，当游戏角色的属性大于关卡最高上限时，可以强行通过该关卡，又或者拥有通过该关卡的必过道具（并不是消耗品）。每个关卡通过后可能会开启一个或多个后置关卡，但每个关卡开启也需要若干个前置关卡，只有前置关卡全部通过后，才能开启该关卡。特别注意，除了一号关卡，如果一个关卡没有任何前置关卡，那么这个关卡则永远无法开启。

每个关卡仅能游玩一次，且每个关卡通过都会增强小沙角色的属性，也会给予一个必过道具。目前小沙正在一号关卡，请问小沙能否将这个游戏打通。

Input

第一行输入两个正整数 $n$ , $s$ ，其中： $n\leq 5\times 10^{4},s\leq 100$ 。

接下来 $n$ 行，每行输入两个正整数 $a_{i},b_{i}$ ，分别代表第 $i$ 关暴力通过需要的属性值，以及该关卡所需的必过道具，其中： $a_{i}\leq 10^{6},b_{i}\leq n$ 。

接下来 $n$ 行，每行输入两个正整数 $c_{i},d_{i}$ ，分别代表通过第 $i$ 关后，可以增加的属性值，以及可以获得的必过道具，其中： $c_{i}\leq 10^{6},d_{i}\leq n$ 。

接下来 $n$ 行，每行首先输入一个非负整数 $k$ ，代表有多少个后置关卡，随后 $k$ 个整数代表第 $i$ 关的后置关卡。其中： $k\leq 10$ ，后置关卡号小于等于 $n$ 。

Output

如果能够通关输出Yes，否则输出No。

Example

input

output

Yes

Tutorial

先考虑入度，判断是否除1点外入度都不为0并且1点入度为0。

然后假设没有通关道具，跑拓扑排序时，把解锁关卡装入优先队列（通关能量小的优先），若通关能量最小的关卡无法通关，挑战失败。

再考虑通关道具，若先解锁关卡后得到通关道具，则把通关能量调为0再次装入优先队列，若先拿到通关道具，则更改通关能量为0即可。

全部关卡通关挑战成功。

Code

#include<bits/stdc++.h>

using namespace std;

typedef pair<long long, int> pli;
const int maxn = 5e4+1;

vector<int> g[maxn], G[maxn];
int d[maxn];

struct node{
    long long to, ti;
};
struct nd{
    long long a, b, c, d;
}p[maxn];

bool vis[maxn], uis[maxn];
long long s, ti;

void bfs() {
    priority_queue<pli, vector<pli>, greater<pli> > que;
    que.push({p[1].a, 1});
    while(!que.empty()) {
        pli t = que.top();
        que.pop();
        if (s <= t.first) {
            cout << "No";
            return ;
        }
        if (vis[t.second]) continue;
        vis[t.second] = true;
        s += p[t.second].c;
        if (!uis[p[t.second].d]) {
            uis[p[t.second].d] = true;
            for(auto to: G[p[t.second].d]) {
                p[to].a = 0;
                if (!d[to]) que.push({p[to].a, to});
            }
        }
        for(auto to: g[t.second]) {
            if (-- d[to] == 0) {
                que.push({p[to].a, to});
            } 
        }
    }
    cout << "Yes";
}   


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n >> s;
    for(int i = 1; i <= n; ++ i) {
        cin >> p[i].a >> p[i].b;
        G[p[i].b].push_back(i);
    }
    for(int i = 1; i <= n; ++ i) {
        cin >> p[i].c >> p[i].d;
    }
    for(int i = 1; i <= n; ++ i) {
        int k;
        cin >> k;
        for(int j = 1; j <= k; ++ j) {
            int v;
            cin >> v;
            g[i].push_back(v);
            d[v] ++;
        }
    }
    bool flag = true;
    for(int i = 2; i <= n; ++ i) {
        if (!d[i]) flag = false;
    }
    if (d[1]) flag = false;
    if (!flag) cout << "No";
    else bfs();
    return 0;
}