### 问题描述 为庆祝蓝桥周赛的举办，大厅中挂满了 $n$ 个填充空气的气球。第 $1$ 号气球被粘在天花板上，其他气球则用绳子挂在比它编号小的气球上。为了防止气球被扯破，**每个气球上方最多只能连着一根绳子**。 小明觉得气球太多了，于是决定拿走一些。小明有两种方式可以拿走气球： 1. 割断一根绳子，这根绳子下方的所有气球都会掉落。小明可以将这些气球全部拿走。 2. 戳破一个气球，这根气球下方的所有气球都会掉落。当然，被戳破的气球本身是无法拿走的。 由于主办方财大气粗，每一根绳子和每一个气球都采用了不同的材料。对于第 $i$ 根绳子，小明需要花费 $w_i$ 的力气来割断它。对于第 $j$ 个气球，小明需要花费 $a_j$ 的力气来戳破它。 小明最多能使出 $W$ 点力气，他想知道他最多能拿走多少个气球。 ### 输入格式 第一行包含两个整数 $n,W$，代表有 $n$ 个气球, 小明最多能使出 $W$ 点力气。（$1\leq n,W \leq 5000$）。 接下来一行包含 $n$ 个整数 $a_1,a_2,…,a_n$，表示戳破每个气球需要的力气。（$1\le a_i\le 5\times10^3$）。 接下来 $n-1$ 行每行包含 $2$ 个整数 $\lbrace u_i,w_i\rbrace$ , 表示编号为 $i+1$ 的气球上端连着第 $u_i$ 个气球，割断这根绳子需要 $w_i$ 点力气。（$1\le u_i\le n,1\le w_i\le 5\times 10^3$）。 ### 输出格式 输出仅一行，包含一个整数，表示答案。 ### 样例输入 ```text 8 6 9 6 1 2 1 1 2 1 1 5 1 1 1 5 2 2 2 1 4 1 4 2 ``` ### 样例输出 ```text 5 ``` ### 说明 花 $2$ 点力气割断第气球 $2$ 和气球 $5$ 之间的绳子，获得 $5$ 这一个气球。 花 $1$ 点力气割断第气球 $2$ 和气球 $6$ 之间的绳子，获得 $6$ 这一个气球。 花 $1$ 点力气割断第气球 $1$ 和气球 $3$ 之间的绳子，获得 $3$ 这一个气球。 花 $2$ 点力气割戳破气球 $4$，获得 $7$ 和 $8$ 两个气球。 故样例输出 $5$ 。