{"raw_statement":[{"iden":"statement","content":"小 A 有一棵 $N$ 个点的带边权的树，树的每个节点有重量 $w_i$ 和价值 $v_i$。\n\n现在小 A 要从中选出若干个节点形成一个集合 $S$，满足这些节点重量之和 $\\leq M$ 并且构成一个连通块。小 A 是一个完美主义者，因此他只会选择节点价值之和最大的那些 $S$。我们称这样的集合 $S$ 为完美的集合。\n\n现在小 $A$ 要从所有完美的集合中选出 $K$ 个，并对这 $K$ 个完美的集合分别进行测试。在这 $K$ 次测试开始前，小 A 首先需要一个点 $x$ 来放置他的测试装置，这个测试装置的最大功率为 $Max$。\n\n接下来的每次测试，小 A 会对测试对象 $S$ 中的所有点进行一次能量传输，对一个点 $y$ 进行能量传输需要的功率为 $dist(x,y)\\times v_y$，其中 $dist(x,y)$ 表示点 $x,y$ 在树上的最短路长度。因此，如果 $S$ 中存在一个点 $y$，满足 $dist(x,y)\\times v_y>Max$，测试就会失败。同时，为了保证能量传输的稳定性，测试装置所在的点 $x$ 需要在集合 $S$ 中，否则测试也会失败。\n\n现在小 A 想知道，有多少种从所有完美的集合选出 $K$ 个的方法，使得他能找到一个放置测试装置的点，来完成他的测试呢？\n\n你只需要输出方案数对 $11920928955078125$ 取模的结果。"},{"iden":"input","content":"第一行四个正整数，表示 $N,M,K,Max$。\n\n接下来一行 $N$ 个正整数，表示 $w_1,\\dots,w_N$。\n\n接下来一行 $N$ 个**非负**整数，表示 $v_1,\\dots,v_N$。\n\n接下来 $N-1$ 行，每行三个正整数 $A_i,B_i,C_i$，表示树上存在一条长度为 $C_i$ 的边连接节点 $A_i,B_i$。"},{"iden":"output","content":"一个数，表示方案数第 $11920928955078125$ 取模的结果。"},{"iden":"note","content":"### 样例解释\n\n完美的集合有 $\\{1,2,5\\},\\{1,4\\},\\{2,6\\}$。\n\n从中选出 $K$ 个且能完成测试的方案为选择 $\\{1,2,5\\},\\{1,4\\}$ 或选择 $\\{1,2,5\\},\\{2,6\\}$。\n\n### 数据范围\n\n|子任务编号\t|\t$N\\leq$\t|\t$M\\leq$\t|\t$K\\leq$\t|\t\t特殊性质\t\t\t|\t分值\t\t|\n|:----------------:|:----------------:|:----------------:|:----------------:|:-----------------------------------:|:----------------:|\n|\t$1$\t\t|\t$17$\t|\t$150$\t|\t$10^9$\t|\t\t\t\t\t\t|\t$13$\t|\n|\t$2$\t\t|\t$60$\t|\t$10000$\t|\t$1$\t\t|\t\t\t\t\t\t|\t$11$\t|\n|\t$3$\t\t|\t$60$\t|\t$2$\t\t|\t$10^4$\t|\t$w_1=\\dots=w_N=1$\t|\t$19$\t|\n|\t$4$\t\t|\t$40$\t|\t$1200$\t|\t$10^9$\t|\t\t\t\t\t\t|\t$20$\t|\n|\t$5$\t\t|\t$60$\t|\t$10000$\t|\t$10^4$\t|\t\t\t\t\t\t|\t$15$\t|\n|\t$6$\t\t|\t$60$\t|\t$10000$\t|\t$10^9$\t|\t\t\t\t\t\t|\t$22$\t|\n\n对于 $100\\%$ 的数据，$N\\leq 60$，$M\\leq 10000$，$C_i\\leq 10000$，$K,w_i,v_i\\leq 10^9$，$Max\\leq 10^{18}$。"}],"translated_statement":null,"sample_group":[["7 3 2 4\n1 1 2 2 1 2 2\n1 1 1 2 1 2 2\n1 2 1\n1 3 2\n1 4 2\n2 5 1\n2 6 2\n4 7 3","2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}