소포 포장

면접 대비

시간 제한1초메모리 제한128 MB

요약

1x1부터 6x6까지 정사각형 제품의 개수가 주어질 때, 모두 담는 데 필요한 6x6 택배 상자의 최소 개수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 구현, 수학, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

어떤 공장은 높이가 모두 $h$ 로 같고 밑면이 $1\times1$ , $2\times2$ , $3\times3$ , $4\times4$ , $5\times5$ , $6\times6$ 인 정사각형 제품을 생산한다. 이 제품들은 항상 높이가 같은 $h$ 이고 밑면이 $6\times6$ 인 정사각형 소포에 담겨 고객에게 배송된다. 운송 비용 때문에 주문된 제품을 배송하는 데 필요한 소포의 개수를 최소로 줄이는 것이 공장과 고객 모두에게 이득이다. 각 주문에 대해 필요한 소포의 최소 개수를 구하는 프로그램을 작성하라.

입력

입력은 여러 줄로 이루어지며, 각 줄은 하나의 주문을 나타낸다. 각 주문은 공백 하나로 구분된 여섯 개의 정수로 이루어지고, 가장 작은 $1\times1$ 부터 가장 큰 $6\times6$ 까지 각 크기의 제품 개수를 차례로 나타낸다. 입력의 끝은 여섯 개의 0으로 이루어진 줄로 표시된다.

출력

입력의 각 줄(마지막의 0으로만 이루어진 줄은 제외)마다 한 줄씩 출력한다. 각 줄에는 해당 주문을 담는 데 필요한 소포의 최소 개수를 출력한다.

예제1

예제 1

입력

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

예상 출력

2
1