Cho một cây ~N~ đỉnh, trong đó đỉnh ~i~ có giá trị là ~V_i~. Cho một số nguyên ~S~. Gốc của cây là đỉnh ~1~. Đếm số đường đi từ một đỉnh ~u~ đến một đỉnh ~v~ nào đó, với điều kiện ~u~ phải nằm trên đường đi từ ~v~ đến gốc, sao cho tổng giá trị của các nút trên đường đi bằng ~S~.

Input

• Dòng đầu tiên chứa hai số ~N~ và ~S~
• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa hai số ~P_i~, Vi là đỉnh cha của đỉnh ~i~ và giá trị của đỉnh ~i~. Ta quy ước ~P_1~ = ~0~.

Output

In ra một số duy nhất là số đường đi tìm được.

Giới hạn

• ~1 \le N \le 1\,000\,000~
• Mọi tổng giá trị của các nút trên đường đi từ ~u~ đến ~v~, trong đó ~u~ nằm trên đường đi từ ~v~ đến gốc, luôn nằm trong phạm vi số nguyên 32 bit có dấu.

Sample Input

5 3
0 1
1 2
2 1
1 -2
4 5

Sample Output

3

Note

Có 3 đường đi là ~1-2, 2-3, 4-5~