Four Gate Push

면접 대비

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

요약

광물과 가스 예산, 유닛별 강도가 주어질 때 세 유닛 종류의 개수를 음이 아닌 정수로 정해 총 강도를 최대로 만든다.

문제

실시간 전략 게임에서 프로토스 병력을 준비하고 있습니다. 병력은 광전사(Zealot), 추적자(Stalker), 파수기(Sentry) 세 종류의 유닛으로 구성됩니다. 각 유닛은 미네랄과 가스라는 두 자원을 일정량 소모하며, 병력에 고정된 전투력을 더해 줍니다.

각 유닛은 0개 이상 원하는 만큼 생산할 수 있습니다. 현재 보유한 미네랄과 가스의 양, 그리고 각 유닛이 더해 주는 전투력이 주어질 때, 얻을 수 있는 최대 병력 전투력을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 한 줄에 하나씩 주어집니다. 각 줄에는 다섯 개의 정수 M, G, Z, S, E가 있습니다.

M ( $0 \le M \le 50000$ ): 보유한 미네랄의 양
G ( $0 \le G \le 50000$ ): 보유한 가스의 양
Z ( $0 \le Z \le 1000$ ): 광전사 한 기의 전투력
S ( $0 \le S \le 1000$ ): 추적자 한 기의 전투력
E ( $0 \le E \le 1000$ ): 파수기 한 기의 전투력

입력의 마지막에는 다섯 정수가 모두 0인 줄( $M = G = Z = S = E = 0$ )이 주어지며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 얻을 수 있는 최대 병력 전투력을 한 줄에 하나씩 출력하세요. 이 값은 유일하게 결정됩니다.