信号放大器

题目描述

树型网络是最节省材料的网络。所谓树型网络,是指一个无环的连通网络,网络中任意两个结点间有且仅有一条通信道路。 网络中有一个结点是服务器,负责将信号直接或间接地发送到各终端机。如图上方,server 结点发出一个信号给结点 $a$ 和 $c$,$a$ 再转发给 $b$。如此,整个网络都收到这个信号了。 ![](https://cdn.luogu.com.cn/upload/image_hosting/e4vb2e7t.png) 但是,实际操作中,信号从一个结点发到另一个结点,会出现信号强度的衰减。衰减量一般由线路长度决定。 如图下方,边上所标的数字为边的衰减量。假设从 server 出发一个强度为 $4$ 个单位的信号,发到结点 $a$ 后强度衰减为 $4-3=1$ 个单位。结点 $a$ 再将其转发给结点 $b$。由于信号强度为 $1$,衰减量为 $2$,因此信号无法发送到 $b$。 一个解决这一问题的方法是,安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度(从服务器出发时的强度)。 上图中,若在结点 $a$ 处安装一个信号放大器,则强度为 $4$ 的信号发到 $a$ 处,即被放大至 $4$。这样,信号就可以被发送的网络中的任意一个节点了。为了简化问题,我们假定每个结点只处理一次信号,当它第二次收到某个信号时,就忽略此信号。 你的任务是根据给出的树型网络,计算出最少需要安装的信号放大器数量。

输入输出格式

输入格式


第一行一个整数 $n$,表示网络中结点的数量。($n \le 20000$) 第 $2 \sim n+1$ 行,每行描述一个节点的连接关系。其中第 $i+1$ 行,描述的是结点 $i$ 的连接关系:首先一个整数 $k$,表示与结点 $i$ 相连的结点的数量。此后 $2k$ 个数,每两个描述一个与结点 $i$ 相连的结点,分别表示结点的编号(编号在 $1 \sim n$ 之间)和该结点与结点 $i$ 之间的边的信号衰减量。结点 $1$ 表示服务器。 最后一行,一个整数,表示从服务器上出发信号的强度。

输出格式


一个整数,表示要使信号能够传遍整个网络,需要安装的最少的信号放大器数量。 如果不论如何安装信号放大器,都无法使信号传遍整个网络,则输出 `No solution.`。

输入输出样例

输入样例 #1

4
2 2 3 3 1
2 1 3 4 2
1 1 1
1 2 2
4

输出样例 #1

1