题目描述

一年一度的武林大会就要召开了，有 $n$ 位武林人士申请加入武林大会。作为本场武林大会唯一的特派员，你被要求从 $n$ 位武林人士中选拔出一些人来作为这次大会的特邀嘉宾（本题中，每位武林人士都有一个对应的编号，编号从 $1$ 到 $n$）。

每位武林人士都有一个声望值，其中第 $i$ 位武林人士的声望值为 $a_i(-10^4 \le a_i \le 10^4)$。看到这里，你也许会问：“为什么武林人士的声望值会是负数呢？” —— 这是因为：有的武林人士行侠仗义，威名远播，所以他们的声望值肯定是正数，但是有些武林人士作恶多端，那他们的声望值就是负的，有些武林人士目前正被奸人污蔑，还没有洗清冤屈，所以他们的声望值暂时也是负的……

武林大会需要有一定的影响力，所以你需要让所有来参加这次武林大会的武林人士的声望值之和大于等于 $X$；否则你将有可能因为办事不力而无法连任特派员的职务。

这 $n$ 位武林人士之间存在着一些师徒关系（每个人最多有一个师父，但是可能有多个徒弟）。为了多打感情牌，你希望在满足参会人员声望值之和 $\ge X$ 的前提下参会人员中师徒对数尽可能地多。比如，如果有三个人 $A,B,C$ 参会，且 $A$ 是 $B$ 的师父，$B$ 是 $C$ 的师父，则这三个人中共有两对师徒（其中 $A$、$B$ 两人构成一对，$B$、$C$ 两人构成一对）。

求：在保证参会的武林人士声望值之和 $\ge X$ 的前提下，参会人员中最多能有多少对师徒？

输入格式

输入的第一行包含两个整数 $n$ 和 $X$，以一个空格分隔，分别表示申请加入武林大会的人数和要求的声望值之和的最小值（$1 \le n \le 500, 1 \le X \le 10^6$）。

接下来 $n$ 行，每行包含两个整数，以一个空格分隔。其中第 $i$ 行的第一个整数表示第 $i$ 位武侠的声望值 $a_i(-10^4 \le a_i \le 10^4)$，第二个整数表示第 $i$ 位武林人士的师父的编号 $b_i(0 \le b_i \le n)$，当 $b_i = 0$ 时，表示第 $i$ 位武侠的师父没有在这 $n$ 个人当中。

输出格式

如果无论如何都无法让参会的武林人士的声望值之和 $\ge X$，输出一个整数 $-1$ 。

否则，输出一个整数，表示在参会的武林人士声望值之和 $\ge X$ 的前提下，他们中师徒对数的最大值。

样例

5 8
-1 0
3 1
5 1
-3 3
2 0

2

样例 1 解释

可以选择邀请第 $1,2,3,5$ 位武林人士参会，此时他们的声望值之和 $-1+3+5+2=9 \ge 8$，且共有两对师徒关系（$(1,2)$ 和 $(1,3)$）。
虽然邀请第 $2,3,5$ 位武林人士参会声望值更大，但是这个组合里没有师徒关系。

数据范围

• 对于 $20\%$ 的数据，$1 \le n \le 10$；
• 对于 $40\%$ 的数据，$1 \le n \le 100$；
• 对于 $100\%$ 的数据，$1 \le n \le 500, 1 \le X \le 10^6, -10^4 \le a_i \le 10^4, 0 \le b_i \le n$。

数据保证师徒关系中不会存在环，即不会出现：“一个人的师父的师父的……师父是他自己”的情况。