В долине Золотоискателей находятся N
ярко выраженных мест добычи золота, каждое из которых представляет собой
квадрат 1 ´ 1. Каждое такое место характеризуется величиной Ai — средним годовым доходом от продажи
добытого золота.
Американский миллионер Скрудж Макдак хочет приобрести в
долине Золотоискателей квадратный участок, на территории которого
находился бы такой набор мест добычи золота, чтобы их суммарный средний годовой
доход был не менее величины W. Конечно, искомый
участок должен иметь минимальную площадь.
Требуется написать программу, с помощью которой можно
найти расположение искомого участка.
Формат входных данных:
В первой строке входного файла содержатся разделённые пробелом
два целых числа, N и W
(1 £ N £ 200; 1 £ W £ 20 000). В следующих N
строках описаны места добычи золота — координаты левой нижней вершины
соответствующего квадрата (Xi, Yi) и значение величины Ai
(1 £ Xi, Yi £ 10 000; 1 £ Ai £ 100).
Все три числа, Xi, Yi, Ai
являются целыми и разделены пробелом. Стороны всех единичных квадратов,
являющихся местами добычи золота, параллельны осям координат.
Формат выходных данных:
Стороны искомого квадратного участка должны быть параллельны
осям координат и иметь целые координаты. В выходном файле в единственной строке
должна содержаться фраза "NO SOLUTION",
если искомый участок не существует, или должны располагаться через пробел
четыре целых числа — координаты левого нижнего и правого верхнего углов искомого
участка. Если решений несколько, необходимо вывести любое.
Пример файлов входных и выходных данных:
|
INPUT
|
OUTPUT
|
|
4 5
1 1 1
3 4 4
3 1 4
2 2 3
|
2 1 4 3
|
|
4 100
1 1 1
3 4 4
3 1 4
2 2 3
|
NO SOLUTION
|
|
3 5
1 1 3
3 1 3
5 1 3
|
1 -1 4 2
|
|
3 5
1 1 3
1 3 3
1 5 3
|
-1 1 2 4
|
