F. Карточная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компьютерные коллекционные карточные игры недавно стали очень популярны. Вот и Вова решил попробовать сыграть в одну такую.

В коллекции Вовы n карт, каждая из которых характеризуется своей силой pi, магическим числом ci и уровнем li. Вова хочет собрать колоду с суммарной силой не менее k, однако магические числа, записанные на картах, могут не позволить ему это сделать — нельзя взять в колоду две карты, если сумма магических чисел, записанных на них, является простым числом. Также Вова не может брать в колоду карты, уровень которых выше уровня его персонажа.

Сейчас у персонажа Вовы 1-й уровень. Помогите Вове определить, до какого уровня ему необходимо развиться, чтобы собрать колоду необходимой силы.

Входные данные

В первой строке входного файла записаны два числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100000).

Далее следуют n строк, каждая из которых содержит три числа — параметры соответствующей карты: pi, ci и li (1 ≤ pi ≤ 1000, 1 ≤ ci ≤ 100000, 1 ≤ li ≤ n).

Выходные данные

Если Вова не сможет собрать колоду необходимой силы, выведите  - 1. Иначе выведите минимальный уровень, при котором это возможно.

Примеры
Входные данные
5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1
Выходные данные
4
Входные данные
3 7
4 4 1
5 8 2
5 3 3
Выходные данные
2