Jaś 和 Małgosia 要去旅行。男孩为了给同伴留下好印象，决定把他们的东西都装进一个背包里。而且，这个背包装得越重，效果就越好。当然，Jaś 不能毫无顾忌地把家里所有东西都装进去——毕竟背包有可能会被撑坏（那会有多丢人啊！）。

此外，Jaś 还不能出现比如带了收音机却没带电池，或者带了三脚架却忘了相机的情况。对于每个物品 $i$，Jaś 要么指定了另一个物品 $j$，如果没有 $j$，则物品 $i$ 就会变得毫无用处；要么直接标明 $i$ 是本身就有用的物品。

请帮助我们的主角，计算在不超过背包最大承重且不带任何无用物品的情况下，背包最多可以装下多重的物品。

输入格式

输入的第一行包含两个整数 $n$ 和 $p$（$1 \le n \le 200$，$1 \le p \le 10^{6}$），分别表示 Jaś 考虑带的物品数量以及背包的最大承重（单位：千克）——如果所带物品总重超过 $p$，背包会被撑坏。

我们假设物品按 $1$ 到 $n$ 编号。接下来的 $n$ 行，每行描述一个物品——编号为 $i$ 的物品由两个整数 $j_{i}$ 和 $m_{i}$（$0 \le j_{i} < i$，$1 \le m_{i} \le p$）表示，分别是：如果要把物品 $i$ 装进背包，必须先有编号为 $j_{i}$ 的物品在背包里（若 $j_{i} = 0$，则物品 $i$ 可无条件带上）；以及物品 $i$ 的重量（单位：千克）。

输出格式

你的程序应输出一个整数：在满足所有条件下，Jaś 能装进背包的最大物品总重量（单位：千克）。

样例

输入

7 11
0 3
0 1
2 3
2 2
4 4
5 3
5 2

输出

10