Задача №112042. Конфеты
Кондитерская фабрика города П, в котором живет Петя, делает очень вкусные конфеты. Как-то раз, Петя собрался в гости к своему другу Васе, который живет в городе М. От города П до города М Петя решил доехать на поезде и взять с собой в подарок как можно больше коробок вкусных конфет.
Каждая коробка конфет имеет размеры \(a\) × \(b\) × \(c\) сантиметров, где \(a\) – длина, \(b\) – ширина и \(c\) – высота коробки. Для перевозки конфет Петя хочет использовать один большой ящик в форме прямоугольного параллелепипеда. В ящик должны быть уложены все коробки конфет. Для того чтобы не повредить их, все коробки в ящике должны сохранять исходную ориентацию и располагаться в одном направлении. Петя может использовать ящик любого размера, но по правилам железнодорожных перевозок размер ящика по сумме трех измерений не может превышать \(N\) сантиметров.
Требуется написать программу, которая по заданным числам \(N\), \(a\), \(b\) и \(с\) определяет такой размер ящика, который должен использовать Петя, чтобы в него поместилось максимальное количество коробок конфет.
Первая строка входного файла содержит разделенные пробелами четыре целых числа: \(N\), \(a\), \(b\), \(с\) (1 ≤ \(N\), \(a\), \(b\), \(c\) ≤ \(10^9\)).
Выходной файл должен содержать три числа – длину, ширину и высоту ящика, который должен выбрать Петя и в который поместится максимальное количество коробок конфет. Если подходящих ответов несколько, необходимо вывести любой.
В первом примере выгоднее всего взять ящик размером 3 × 4 × 3 сантиметров, в который поместится три коробки конфет в длину, две коробки конфет в ширину и одна коробка конфет в высоту.
Во втором примере для того, чтобы разместить хотя бы две коробки конфет, нужен ящик размером хотя бы 8 × 3 × 4, у которого сумма измерений равна 15. В подходящий ящик поместится максимум одна коробка конфет. Подходящим также является ящик размером 9 × 3 × 2, хотя он и не является минимальным.
Частичные правильные решения для тестов, в которых \(N\) ≤ 1000, будут оцениваться из 30 баллов.
Частичные правильные решения для тестов, в которых \(N\) ≤ 100 000, будут оцениваться из 60 баллов.
10 1 2 3
3 4 3
14 8 3 2
8 3 2