codeforces487A

Fight the Monster

A monster is attacking the Cyberland!

Master Yang, a braver, is going to beat the monster. Yang and the monster each have 3 attributes: hitpoints (HP), offensive power (ATK) and defensive power (DEF).

During the battle, every second the monster's HP decrease by max(0, ATK_Y - DEF_M), while Yang's HP decreases by max(0, ATK_M - DEF_Y), where index Y denotes Master Yang and index M denotes monster. Both decreases happen simultaneously Once monster's HP ≤ 0 and the same time Master Yang's HP > 0, Master Yang wins.

Master Yang can buy attributes from the magic shop of Cyberland: h bitcoins per HP, a bitcoins per ATK, and d bitcoins per DEF.

Now Master Yang wants to know the minimum number of bitcoins he can spend in order to win.

Input

The first line contains three integers HP_Y, ATK_Y, DEF_Y, separated by a space, denoting the initial HP, ATK and DEF of Master Yang.

The second line contains three integers HP_M, ATK_M, DEF_M, separated by a space, denoting the HP, ATK and DEF of the monster.

The third line contains three integers h, a, d, separated by a space, denoting the price of 1 HP, 1 ATK and 1 DEF.

All numbers in input are integer and lie between 1 and 100 inclusively.

Output

The only output line should contain an integer, denoting the minimum bitcoins Master Yang should spend in order to win.

Examples

Input

1 2 1
1 100 1
1 100 100

Output

Input

100 100 100
1 1 1
1 1 1

Output

Note

For the first sample, prices for ATK and DEF are extremely high. Master Yang can buy 99 HP, then he can beat the monster with 1 HP left.

For the second sample, Master Yang is strong enough to beat the monster, so he doesn't need to buy anything.

sol：一开始想了好几个SB贪心都被自己否定掉了，猛然发现数据范围小的不像话，暴力枚举n²即可

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int inf=0x3f3f3f3f;
struct Record
{
    int Hp,Atk,Def;
}a,b,Buy;
int main()
{
    int i,j,k,ans=inf;
    R(a.Hp); R(a.Atk); R(a.Def);
    R(b.Hp); R(b.Atk); R(b.Def);
    R(Buy.Hp); R(Buy.Atk); R(Buy.Def);
    for(i=1;i<=b.Hp;i++)//几回合干掉怪兽
    {
        int ATK=(b.Hp/i+(bool)(b.Hp%i))+b.Def;
        for(j=0;j<=b.Atk;j++)//增加几点防御
        {
            int DEF=a.Def+j;
            int Sum=max(ATK-a.Atk,0)*Buy.Atk+j*Buy.Def;
            int Hp=max(b.Atk-DEF,0)*i+1;
            ans=min(ans,Sum+max(Hp-a.Hp,0)*Buy.Hp);
        }
    }
    Wl(ans);
    return 0;
}
/*
Input
1 2 1
1 100 1
1 100 100
Output
99

Input
100 100 100
1 1 1
1 1 1
Output
0
*/

View Code