数字集换式卡牌游戏最近变得非常流行。因此 Vova 决定尝试其中一种。
Vova 收藏了 n 张卡片。每张卡牌的特征都是其力量 pi、魔法数字 ci 和等级 li。 Vova 想要构建一副总功率不小于 k 的牌组,但魔法数字可能不允许他这样做——如果这些牌上写的魔法数字之和是素数,Vova 就无法将两张牌放入一副牌中。此外,如果卡牌的等级高于 Vova 角色的等级,Vova 也无法使用该卡牌。
目前Vova的角色等级为1。帮助Vova确定他需要达到的最低等级,才能构建具有所需总功率的套牌。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100000)。
接下来是 n 行,每行包含三个数字,分别代表对应的牌:pi、ci 和 li (1 ≤ pi ≤ 1000, 1 ≤ ci ≤ 100000, 1 ≤ li ≤ n)。
输出
如果 Vova 无法构建具有所需功率的牌组,请打印 - 1。否则打印 Vova 必须达到的最低级别才能构建牌组。
示例
输入 #1
5 8 5 5 1 1 5 4 4 6 3 1 12 4 3 12 1
输出 #1
4
输入 #2
3 7 4 4 1 5 8 2 5 3 3
输出 #2
2