题目描述

将地图上的所有地点标号为$1$到$n$，地图中有$n-1$条双向道路连接这些点，通过一条双向道路需要一定时间，保证从任意一个点可以通过道路到达地图上的所有点。 有些点上可能有资源，到达一个有资源的点后，可以获取资源来增加 $w_i$的武力值。资源被获取后就会消失，获取资源不需要时间。可选择不获取资源。 有些点上可能有敌人，到达一个有敌人的点后，必须花费$t_i$秒与敌人周旋，并将敌人消灭。敌人被消灭后就会消失。不能无视敌人。 如果一个点上既有资源又有敌人，必须先消灭敌人才能获取资源。 游戏开始时Y君可以空降到任意一个点上，接下来，有T秒时间行动，Y君希望游戏结束时，武力值尽可能大。

输入

第一行由单个空格隔开的两个正整数 $n,T$，代表点数和时间。 第二行$n$个由单个空格隔开的非负整数代表 $w_i$，如果$w_i=0$表示该点没有资源。 第三行$n$个由单个空格隔开的非负整数代表 $t_i$，如果$t_i=0$代表该点没有敌人。 接下来$n-1$行每行由单个空格隔开的$3$个非负整数$a，b，c$表示连接$a$和$b$的双向道路，通过这条道路需要$c$秒。

输出

输出一行一个整数代表$T$秒后Y君的武力值。

输入样例

17 54
5 5 1 1 1 25 1 10 15 3 6 6 66 4 4 4 4
0 1 3 0 0 0 1 3 2 0 6 7 54 0 0 0 0
1 8 3
2 8 3
8 7 7
7 13 0
7 14 0
15 14 2
16 14 3
17 14 5
7 9 4
9 10 25
10 11 0
10 12 0
7 6 20
3 6 3
3 4 3
3 5 3

输出样例

68

提示

【数据规模与约定】

测试点	特殊性质
$1$	$w_i = 0$
$2$	$ti=0$
$3$	以$i$为端点的双向道路不会超过两条
$4$
$5$	$2$到$n$号点均有双向道路与$1$相连
$6$
$7$	保证数据随机生成
$8$
$9$	$N/A$
$10$

对于100%的数据，$n,T≤300，0≤w_i,t_i,c≤10^6,1≤a,b≤n$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。