Card Game

题面翻译

题目描述

集卡游戏最近十分流行。所以 Vova 决定尝试这其中的一款游戏。

Vova 的收藏中有 $n$ 张卡片。每一张卡上有三个数字，分别代表它的能量 $p_i$，魔力值 $c_i$ 和等级 $l_i$。Vova 想要创建一个总能量不小于 $k$ 的卡组，但是魔力值可能不允许他这样做 — Vova 不能把两张魔力值之和为质数的卡片放在同一个卡组里。他也不能使用（即放进卡组）一张等级高于他自己角色等级的卡片。

现在 Vova 的角色等级为 $1$。帮助 Vova 来求出他需要达到的最小角色等级来创建一套满足总能量条件的卡组。

输入格式

第一行包含两个整数 $n,k\;(1\le n\le100,1\le k\le100000)$。

接下来 $n$ 行，每行包含三个数字来代表一张 Vova 的卡片：$p_i,c_i$ 和 $l_i\;(1\le p_i\le1000,1\le c_i\le 100000,1\le l_i\le n)$。

输出格式

如果 Vova 无论如何不能够创建一个这样的卡组，输出 $-1$ 。
否则输出 Vova 需要达到的最小等级。

题目描述

Digital collectible card games have become very popular recently. So Vova decided to try one of these.

Vova has $n$ cards in his collection. Each of these cards is characterised by its power $p_{i}$ , magic number $c_{i}$ and level $l_{i}$ . Vova wants to build a deck with total power not less than $k$ , but magic numbers may not allow him to do so — Vova can't place two cards in a deck if the sum of the magic numbers written on these cards is a prime number. Also Vova cannot use a card if its level is greater than the level of Vova's character.

At the moment Vova's character's level is $1$ . Help Vova to determine the minimum level he needs to reach in order to build a deck with the required total power.

输入格式

The first line contains two integers $n$ and $k$ ( $1<=n<=100$ , $1<=k<=100000$ ).

Then $n$ lines follow, each of these lines contains three numbers that represent the corresponding card: $p_{i}$ , $c_{i}$ and $l_{i}$ ( $1<=p_{i}<=1000$ , $1<=c_{i}<=100000$ , $1<=l_{i}<=n$ ).

输出格式

If Vova won't be able to build a deck with required power, print $-1$ . Otherwise print the minimum level Vova has to reach in order to build a deck.

样例 #1

样例输入 #1

5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1

样例输出 #1

4

样例 #2

样例输入 #2

3 7
4 4 1
5 8 2
5 3 3

样例输出 #2

2