A11058 | Card Game

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.