题面描述:

在这道题目中，给定了一组以树形结构表示的云服务，每个节点记录着不同级别的问题及其数量。通过计算每个云服务的DI值（遗留问题缺陷密度），公式为 $\text{DI值} = 5 * \text{严重问题数} + 2 * \text{一般问题数}$，判断其是否大于阈值，从而评估该云服务是否为风险服务。输入包括一个阈值和若干节点的信息，要求输出被评定为风险云服务的数量。

思路

给定一个森林（多棵树），要求统计所有节点的计算值的和超过阈值的树的数量。

我们从树的根节点出发，遍历树的每一个子节点，在回溯时将其严重问题和一般问题的数量记录到父节点上。这样在遍历完一棵树后，根节点就包含了整棵树严重问题和一般问题的数量。按照公式计算是否超过阈值即可。

题目描述

$\qquad$要是你认为小明只做网站，那就大错特错了。其实小明还做点云服务，最近，小明忙着维护云服务器，没空跟你开黑。为了上分，你打算出手。

$\qquad$小明将云服务看做一棵树，每个云服务在发布前尚未解决的问题称为云服务的遗留问题（云服务的遗留问题包含以该云服务为根节点的树上所有节点的问题），DI值（遗留问题缺陷密度）可以作为评估云服务发布的指标，当云服务DI值小于等于阈值时才准许云服务发布，否则视为风险云服务，需要问题整改完成后重新进行发布评估。现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。

$\qquad$计算公式：DI值=5×严重问题数＋2×一般问题数，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。

输入描述

$\qquad$第一行输入$M$和$N$($M \le 100000$，$N \le 1000$)，使用空格分隔，M表示代表云服务阈值，N表示接下来有N行问题统计数据；

$\qquad$接下来输入一个$N∗4$的矩阵表，行内使用空格分隔，第一列$A_i$为服务节点，第二列$B_i$为$A_i$的父节点，如果$A_i$为云服务则无父节点，此时Bi用∗号表示($A_i$和$B_i$取值为字符串，$1 \le$字符串长度$≤5$，均由小写英文字母或∗号组成)，第三列$C_i$为问题级别（$C_i$取值为{0,1}，0表示严重问题，1表示一般问题），第四列$D_i$为该节点该级别的问题数量(Di≤1000)。

$\qquad$说明：输入保证只出现树的关系，不会出现连通图的情况。

输出描述

$\qquad$输出一个整数，表示风险云服务个数。

样例一

输入

40 12 
a * 0 2 
a * 1 2 
b a 0 3 
b a 1 5 
c a 1 3 
d a 0 1 
d a 1 3 
e b 0 2 
f * 0 8 
f * 1 10 
g f 1 2
h * 0 4

输出

2

解释

$\qquad$（a * 0 2）表示节点a有2个严重问题，*表示无父节点，即a为云服务。（b a 1 5）表示节点b有5个一般问题，b的父节点是a。可以看出，该样例有3个云服务a、f、h。云服务a的子节点有b、c、d、e，严重问题个数为2+3+0+1+2=82+3+0+1+2=8，一般问题个数为2+5+3+3+0=132+5+3+3+0=13，DI值=8∗5+13∗2=66>阈值40，故云服务a是风险云服务；云服务f严重问题个数为8+0=88+0=8，一般问题个数为10+2=1210+2=12，DI值=8∗5+12∗2=64>阈值40，故云服务f也是风险云服务；云服务h严重问题个数为44，一般问题个数为00，DI值=4∗5+0∗2=20<=阈值40，故云服务h不是风险云服务；因此该样例有2个风险云服务。

样例二

输入

50 10 
b a 1 5 
a * 0 2 
b a 0 3 
c a 1 3 
d a 0 1 
a * 1 2 
d a 1 3 
e b 0 2 
f b 1 1 
g c 1 2

输出

1

Limitation

1s, 1024KiB for each test case.