루이지를 위한 선물
면접 대비시간 제한2초메모리 제한1024 MB
네 막대의 길이가 주어질 때 막대를 잘라 만들 수 있는 넓이가 가장 큰 직사각형의 두 변 길이를 구합니다.
문제
마리오는 루이지에게 선물을 주고 싶어 한다. 마리오에게는 길이가 양의 정수인 막대가 네 개 있다. 마리오는 각 막대를 여러 개의 다른 막대로 쪼갤 수 있다. 쪼갠 각 막대의 길이도 양의 정수여야 하며, 쪼갠 막대들의 길이 합은 원래 막대의 길이와 같아야 한다.
그다음 마리오는 쪼갠 막대 중에서 네 개를 골라 직사각형의 변으로 삼는다. 각 변은 고른 막대 하나로만 이루어져야 한다. 루이지는 넓이가 큰 직사각형을 좋아하므로, 마리오는 넓이가 가장 큰 직사각형을 만들려고 한다. 그런 직사각형을 찾는 것을 도와 달라.
입력
한 줄에 공백으로 구분된 양의 정수 , , , 가 주어진다. 이들은 마리오가 처음 가지고 있던 막대의 길이이다 ().
출력
공백으로 구분된 두 정수를 한 줄에 출력한다. 이 두 수는 원래 막대를 적절히 쪼개서 만들 수 있는 넓이가 가장 큰 직사각형의 변 길이이다. 답이 여러 개라면 그중 아무거나 출력해도 된다.
힌트
주어진 테스트에서 최적의 답은 다음과 같이 얻을 수 있다. 두 번째 막대를 길이 2와 6인 막대로 쪼개고, 첫 번째와 세 번째 막대는 그대로 둔다. 네 번째 막대는 길이 1, 9, 9인 막대 세 개로 쪼갠다. 그러면 길이 6, 6, 9, 9인 막대를 골라 변의 길이가 6과 9인 직사각형을 만들 수 있고, 이 직사각형의 넓이가 이 테스트에서의 최댓값이다.