H-拯救萝莉(easy version)_牛客2022年儿童节比赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题有对应的hard version，区别仅在于easy version多一个额外限制条件，见输入描述，保证easy version的测试用例集是hard version的子集。

邪恶的魔王抓走了所有的小萝莉，并且把她们关在了 $N$ 个城堡中，不过好消息是，清楚姐姐现在已经占领了 $1$ 号城堡，并且在城堡中训练一些士（群）兵（友）来作战。

城堡与城堡之间有 $M$ 条单向运兵线路，清楚姐姐只能按照这些单向道路派兵攻打敌方城堡。

这 $N$ 个城堡的分布结构呈一张有向无环图（DAG）的结构，并且保证从 $1$ 号城堡出发可以通过单向道路到达其他 $N-1$ 个城堡中。

对于除了 $1$ 号城堡以外的每一个城堡，都被大魔王控制，每一座城堡有三个属性：防御力 $D$ ，敌人总数 $A$ ，以及人口数 $P$ 。

清楚姐姐在任意时刻都可以进行如下几个操作

移动：清楚姐姐可以命令自己的士兵按照城堡间的单向道路移动，前提是单向道路两端的城堡均已被清楚姐姐控制或为中立状态。
攻击：清楚姐姐可以选择一个敌方控制的目标城堡，以及若干个己方已控制且可直接通过运兵路线攻击目标的城堡发动一次攻击，攻击所需的兵力由这若干个城堡随意分配，每次进攻时，若干个己方城堡用于进攻的兵力总和 $S$ 不得少于 $D$ ，我方士兵与敌方死战。

                    若 $S<A$ 则战斗结束后目标城堡的敌人总数变为 $A-S$ ，我方参与本场战斗的士兵全部战死。
                    若 $S=A$ 则战斗结束后目标城堡中我方士兵与敌方士兵全部阵亡，城堡处于无人的中立状态。
                    若 $S>A$ 则战斗结束后目标城堡中我方士兵剩余 $S-A$ ，全歼敌人，可以直接进行“占领”操作。

占领：当我方战斗结束全歼敌人且至少有 $1$ 人存活，或者往中立城堡派出 $1$ 个士兵后，可以进行占领，占领后该城堡变为我方控制状态，且最多可以招募 $P$ 人成为我方士兵，新招募的士兵初始位置位于该占领的城堡。对于已经占领的城堡，可以将所有士兵都调走，即使所有士兵都离开也不会转化为中立状态。
招募：除了一开始的 $1$ 号城堡以外，每一个我方控制的城堡都可以最多招募不多于该城堡人口上限 $P$ 的士兵。

为了拯救小萝莉，清楚姐姐需要占领其余 $N-1$ 个城堡。

现在智乃想知道，清楚姐姐一开始在 $1$ 号城堡中训练多少群友才能达成目标。

有向无环图oi-wiki：https://oi-wiki.org/graph/dag/

牛客竞赛图论课程：https://ac.nowcoder.com/courses/cover/live/740

输入描述:

第一行输入两个正整数表示城堡的数目以及单向运兵路线的数目。
接下来行，每行输入三个非负整数表示从号城堡到号城堡的防御力，敌人总数，以及人口数。
接下来行，每行输入两个正整数表示一条单向运兵线路。
输入保证这些运兵线路构成一个DAG图，且从号城堡可到达所有城堡。
easy version额外限制：保证且对于，城堡到城堡必定存在运兵路线。

输出描述:

仅一行一个整数，表示清楚姐姐一开始在号城堡中训练多少群友才能达成目标。

示例1

输入

复制

输出

复制

说明

一开始训练名群友，派它们攻击号城堡。号城堡的防御力为，所以可以派名群友直接进攻该城堡。
战斗结束后，在号城堡内我方剩余名士兵，占领号城堡并招募人，此时城堡内有人。
最后派人攻击号城堡，在号城堡内我方剩余名士兵，占领该城堡获得胜利。

示例2

输入

复制

2 1
100 1 0
1 2

输出

复制

说明

城堡的防御力为，需要至少人同时进攻才能攻打城堡。

示例3

输入

复制

2 1
1 100 0
1 2

输出

复制

说明

注意至少需要人存活才能占领城堡。

示例4

输入

复制

输出

复制

备注:

有向无环图oi-wiki：https://oi-wiki.org/graph/dag/
牛客竞赛图论课程：https://ac.nowcoder.com/courses/cover/live/740