You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

DDT 快到了！

小 A 还有 n 个任务没有做。小 A 经过评估后发现，完成第 i 个任务最少需要 $l_i$ 分钟，最多需要 $r_i$分钟。

现在小 A 总共还剩 T 分钟：

若在最坏情况下（即每个任务的完成时间都取 $r_i$)能完成所有任务，输出 OK ；

若在平均情况下（即每个任务的完成时间都取 $l_i$, $r_i$的平均数）能完成所有任务，输出 Maybe OK ；若在最好情况下（即每个任务的完成时间都取 $l_i$)能完成所有任务，输出 Maybe ；

否则输出最好情况下最多能完成多少个任务。

输入格式

第一行两个整数 n, T，表示任务数量和剩余时间。

接下来 n 行，第 i 行两个整数$l_i$, $r_i$，表示第 i 个任务最少需要的时间和最多需要的时间。

输出格式

输出一行，一个字符串或一个整数，表示答案。

样例 #1

样例输入 #1

3 10
4 6
1 6
1 2

样例输出 #1

Maybe OK

样例 #2

样例输入 #2

3 10
2 9
6 8
9 10

样例输出 #2

2

提示

数据范围

对于 50% 的数据，n ≤ 100；

对于 100% 的数据，1 ≤ n ≤ 10^5, 1 ≤ T≤ 10^9, 1 ≤ $l_i$ ≤$r_i$ ≤ 10^4。

前 50% 和后 50% 中，题中四种情况均各占 20%, 20%, 30%, 30%。