Problem - 7026

Two heroes are fighting, whose names are hero $0$ and hero $1$ respectively.

You are controlling the hero $0$, and your enemy is the hero $1$. Each hero has five integer attributes: ATTACK, DEFENCE, POWER, KNOWLEDGE, and HEALTH. When two heroes battle with each other, they will take turns to attack and your hero moves first. One hero can make $\pmb{\text{exactly one attack}}$ in one turn, either a physical attack or a magical attack.

Assume their attritubes are $A_i,D_i,P_i,K_i,H_i(0 \leq i \leq 1)$. For hero $i$, its physical attack's damage is $C_p \max(1,A_i-D_{1-i})$ while its magical attack's damage is $C_m P_i$ where $C_p, C_m$ are given constants.

Hero $i$ can make magical attacks no more than $K_i$ times in the whole battle. After hero $i$'s attack, $H_{1-i}$ will decrease by the damage of its enemy. If $H_{1-i}$ is lower or equal to $0$, the hero $(1-i)$ loses and the battle ends.

Now you know your enemy is Yog who is utterly ignorant of magic, which means $P_1=K_1=0$ and he will only make physical attacks. You can distribute $N$ attribute points to four attributes $A_0, D_0, P_0, K_0$ arbitrarily which means these attributes can be any non-negative integer satisfying $0 \leq A_0+D_0+P_0+K_0 \leq N$.

Given $C_p,C_m,H_0,A_1,D_1$ and $N$, please calculate the maximum $H_1$ that you have a chance to win.

Might and Magic