Four Gate Push

Interview

Time limit1sMemory limit128 MB

Summary

Given mineral and gas budgets and per-unit strengths, maximize total strength over non-negative counts of three unit types.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Greedy
Solved: No attempts yet

Problem

In a real-time strategy game you are preparing a Protoss army built from three unit types: zealots, stalkers, and sentries. Each unit costs a fixed amount of two resources — minerals and gas — and adds a fixed amount of strength to your army.

Unit	Minerals	Gas	Strength
Zealot	100	0	Z
Stalker	125	50	S
Sentry	50	100	E

You may build any non-negative number of each unit. Given how many minerals and how much gas you currently have, together with the strength each unit adds, determine the maximum total army strength you can obtain.

Input

The input consists of several test cases, one per line. Each line contains five integers M, G, Z, S, and E:

M ( $0 \le M \le 50000$ ): the amount of minerals you have
G ( $0 \le G \le 50000$ ): the amount of gas you have
Z ( $0 \le Z \le 1000$ ): the strength of one zealot
S ( $0 \le S \le 1000$ ): the strength of one stalker
E ( $0 \le E \le 1000$ ): the strength of one sentry

The input ends with a line of five zeros ( $M = G = Z = S = E = 0$ ), which must not be processed.

Output

For each test case, print on its own line the maximum total army strength you can obtain. This value is uniquely determined.

Examples2

Example 1
Input
```
500 400 10 20 15
0 0 0 0 0
```
Expected output
```
95
```
Example 2
Input
```
100 0 3 0 0
0 0 0 0 0
```
Expected output
```
3
```