만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사탕 상자

시간 제한2초메모리 제한1024 MB

요약
세 변의 합이 N을 넘지 않는 큰 상자를 골라, 같은 방향으로 놓인 a x b x c 사탕 상자를 가장 많이 담는 크기를 구합니다.
난이도

보통10점 중 6점

유형
수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

페탸는 P시에 산다. P시의 사탕 공장은 아주 맛있는 사탕을 만든다. 페탸는 기차를 타고 M시에 사는 친구 바샤를 만나러 갈 계획이다. 선물로 사탕 상자를 가능한 많이 가져가려 한다.

사탕 상자 하나의 크기는 a×b×ca \times b \times c cm이다. 여기서 aa는 길이, bb는 너비, cc는 높이다. 페탸는 직육면체 모양의 큰 상자 하나를 사용한다. 모든 사탕 상자는 이 큰 상자 안에 들어가야 한다. 사탕 상자는 원래 방향을 유지해야 하며, 모두 같은 방향으로 놓여야 한다. 큰 상자의 크기는 자유롭게 정할 수 있지만, 철도 운송 규정에 따라 세 변의 합은 NN cm를 넘을 수 없다.

NN, aa, bb, cc가 주어졌을 때, 사탕 상자를 가장 많이 담을 수 있는 상자의 크기를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 공백으로 구분된 정수 네 개 NN, aa, bb, cc가 주어진다. (1≤N,a,b,c≤1091 \le N, a, b, c \le 10^9)

출력

페탸가 골라야 할 상자의 길이, 너비, 높이를 순서대로 출력한다. 사탕 상자를 가장 많이 담을 수 있는 답이 여러 개라면 그중 아무거나 출력해도 된다.

힌트

첫 번째 예제에서는 3×4×33 \times 4 \times 3 cm 상자가 가장 유리하다. 길이 방향으로 3개, 너비 방향으로 2개, 높이 방향으로 1개의 사탕 상자가 들어간다.

두 번째 예제에서 사탕 상자를 최소 2개 담으려면 상자는 최소 8×3×48 \times 3 \times 4 cm여야 하며, 세 변의 합은 15이다. 이 상자에는 사탕 상자가 최대 1개 들어간다. 9×3×29 \times 3 \times 2 상자도 정답이다. 가장 작은 상자는 아니지만 조건을 만족한다.

예제2

  1. 예제 1

    입력
    10 1 2 3
    
    예상 출력
    3 4 3
    
  2. 예제 2

    입력
    14 8 3 2
    
    예상 출력
    9 3 2