题目描述

小$\red{S}$在一棵被称为$\red{OJT}$的树上刷题。

这棵树上，有$\red{n}$个节点，每个节点上都有一道题目，每个节点上的题目难度可能会不同。

小$\red{S}$的能力有限，仅为$\red{k}$个单位能力，在第$\red{i}$个节点上的题目，难度为$\red{Di}$。由于题目过毒，

每做一道题都会杀死小$\red{S}$的脑细胞，使小$\red{S}$的能力值下降。做第 $\red{i }$个节点上的题目会使他的能力值下降$\red{ci}$个单位。

对于一道题，小$\red{S}$能拿到小$\red{S}$目前的能力值 $\red{/ Di \times 100（}$向下取整）分（若小$\red{S}$目前的能力值$\red{>=Di，}$小$\red{S}$就能拿到$\red{100）}$， 因信号问题，实际的$\red{Di}$为$\red a$,$\red{(\sum^{a}_{i}{\sum^{a}_{j}{(a~ mod ~i)(a~mod~j)}})~mod~100}$

小$\red{S}$希望可以拿到媛量高的总分数，希望你帮他找到他最多可以获得的总分数。

$\red{PS：}$小$\red{S}$总是从根节点$\red{1}$出发，每次向所在节点的其中一个子节点走，小$\red{S}$可以选择不做当前节点上的题目。

输入格式

第一行$\red{n，}$$\red{k，}$表示有$\red{n}$个节点，小$\red{S}$一开始有$\red{k}$的单位能力

接下来$\red{n-1}$行，两个整数$\red{xi,yi,}$表示节点$\red{xi}$和节点$\red{yi}$连了一条边。

接下来一行，$\red{n}$个整数$\red{Di，}$表示在节点$\red{i}$上题目的难度。

接下来一行，$\red{n}$个整数$\red{Ci，}$表示在节点$\red{i}$上题目耗费的精力。

输出格式

一行一个整数，$\red{ans，}$表示小$\red{S}$可以获得的最大总分数。

样例

输入样例

3 90
1 2
2 3
98 90 90
11 2 6

输出样例

274

提示

数据范围

对于$\red{100\%}$的数据，$\red{n<=1000,1<=k,di,ci<=1000, 1<=xi,yi<=n}$