Фермер Джон и его стадо играют в фрисби. Беси бросает фрисби в поле,
и соирается бежать прямо к Марку.
Марк имеет высоту H (1 <= H <= 1,000,000,000), но имеется также N
(2 <= N <= 20) коров из команды Беси вокруг Марка . Они могут поймать
Фрисби, только если став друг на друга, они построят пирамиду высотой
не менее, чем высота Марка.
Каждая из N коров имеет высоту, вес и силу.
Сила указывает максимальный суммарный вес, который может находиться
выше её.
По заданным ограничениям, Беси хочет узнать может ли её команда
построить достаточно большую пирамиду, чтобы поймать фрисби.
И если да, вычислить ещё максимальный коэффициент безопасности
пирамиды.
Максимальный коэффициент безопасности пирамиды - количество веса,
которое может быть добавлено, на её вершину, так чтобы не превысить
силу ни одной из коров.
Формат входных данных
Первая строка ввода содержит N и H.
Каждая из следующих N строк ввода описывает одну корову, задавая
её высоту, вес и силу. Все числа положительные, не превышающие
1 миллиард.
Формат выходных данных
Если команда Беси может построить пирамиду, достаточную, чтобы поймать
фрисби, выведите максимально достижимый фактор безопасности для такой
пирамиды. Иначе выведите фразу "Mark is too tall" (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 10
9 4 1
3 3 5
5 5 10
4 4 5
|
2
|