Компьютерные коллекционные карточные игры недавно стали очень популярны. Вот и Вова решил попробовать сыграть в одну такую.
В коллекции Вовы n карт, каждая из которых характеризуется своей силой pi, магическим числом ci и уровнем li. Вова хочет собрать колоду с суммарной силой не менее k, однако магические числа, записанные на картах, могут не позволить ему это сделать — нельзя взять в колоду две карты, если сумма магических чисел, записанных на них, является простым числом. Также Вова не может брать в колоду карты, уровень которых выше уровня его персонажа.
Сейчас у персонажа Вовы 1-й уровень. Помогите Вове определить, до какого уровня ему необходимо развиться, чтобы собрать колоду необходимой силы.
Выходные данные
Если Вова не сможет собрать колоду необходимой силы, выведите - 1. Иначе выведите минимальный уровень, при котором это возможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1
|
4
|
|
2
|
3 7
4 4 1
5 8 2
5 3 3
|
2
|