You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

核心（$\texttt{center}$）

【题目描述】

小 D 负责管理一个计算机网络，这个计算机网络形成树形结构，该网络由 $n$ 个节点和 $n-1$ 条网线连接，保证任意两个网线都可以通过若干条网线连接。

每条网线 $i$ 有长度 $l_i$，每个节点 $u$ 有价格 $w_u$ 和效率 $v_u$。

定义 $\mathrm{dis}(x,y)$ 表示节点 $x$ 到 $y$ 的简单路径上所有网线的长度之和。

小 D 需要选择若干个节点执行任务，设小 D 选择个节点构成集合 $S$，那么 $S$ 合法当且仅当如下条件满足：

• $S$ 中节点的价格之和不超过 $m$。
• 对于任意 $S$ 中的两个节点，他们之间的简单路径不经过不在 $S$ 中的节点。

小 D 想要执行任务的节点中有一个核心，因此他要求一个合法集合 $S$ 还需要满足：

• 存在至少一个 $u\in S$ 满足：对于所有 $x\in S$，都有 $\mathrm{dist}(x,u)\times v_x\le p$。

小 D 想知道所有合法集合中，选出节点的效率和最大是多少，以及这样的集合有几个。

【输入格式】

从 $\texttt{center.in}$ 中读入数据。

第一行三个整数 $n,m,p$。

第二行 $n$ 个整数，第 $i$ 个表示 $w_i$。

第三行 $n$ 个整数，第 $i$ 个表示 $v_i$。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,l_i$，表示一条连接 $u_i,v_i$ 的网线长度为 $l_i$。

【输出格式】

输出到 $\texttt{center.out}$ 中。

一行两个整数，表示所有合法集合的节点效率的最大值，以及这样的集合个数。

【样例 1 输入】

7 3 4
1 1 2 2 1 2 2
1 1 1 2 1 2 2
1 2 1
1 3 2
1 4 2
2 5 1
2 6 2
4 7 3

【样例1 输出】

3 3

【样例 1 解释】

合法集合为：$\{1,2,5\},\{1,4\},\{2,6\}$。

【样例 2】

见下发文件中的 $\texttt{center2.in}$ 与 $\texttt{center2.ans}$。

该样例满足子任务 $1$ 的限制。

【样例 3】

见下发文件中的 $\texttt{center3.in}$ 与 $\texttt{center3.ans}$。

该样例满足子任务 $2$ 的限制。

【样例 4】

见下发文件中的 $\texttt{center4.in}$ 与 $\texttt{center4.ans}$。

该样例满足子任务 $3$ 的限制。

【样例 5】

见下发文件中的 $\texttt{center5.in}$ 与 $\texttt{center5.ans}$。

该样例满足子任务 $4$ 的限制。

【数据范围】

对于所有的测试数据有：$1\le n\le 60,1\le m,w_i,l_i\le 10^4,0\le v_i\le 10^9,1\le p\le 10^{18}$