Jaś and Małgosia are going on a trip. The boy, wanting to impress his friend, decided to pack their belongings into a single backpack. Moreover, the heavier the backpack, the better the impression he will make. Of course, Jaś cannot pack everything he finds at home without thinking—the backpack might tear (what a shame that would be!).

Furthermore, Jaś cannot allow a situation where, for example, he takes a radio but leaves the batteries behind, or takes a tripod but forgets the camera. For each item $i$, Jaś has either specified another item $j$ without which item $i$ would be useless, or simply noted that $i$ is an item that is useful on its own.

Help our hero calculate the maximum weight of the backpack's contents he can achieve without exceeding its maximum capacity and without taking any useless items.

Input

The first line of input contains two integers $n$ and $p$ ($1 \le n \le 200$, $1 \le p \le 10^{6}$), representing the number of items Jaś is considering taking and the backpack's capacity in kilograms—if we pack items with a total mass exceeding $p$, the backpack will tear.

Assume that the items are numbered from 1 to $n$. The next $n$ lines contain descriptions of the items—the description of item $i$ consists of two integers $j_{i}$ and $m_{i}$ ($0 \le j_{i} < i$, $1 \le m_{i} \le p$), representing the number of the item that must be in the backpack for item $i$ to be packed (if $j_{i} = 0$, then item $i$ can be packed unconditionally), and the mass of item $i$ in kilograms.

Output

Your program should output a single integer: the maximum mass of the backpack's contents (in kilograms) that Jaś can achieve.

Examples

Input 1

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

Output 1

10