#include #include #include #include #include using namespace std; class Data { public: int n1000, n100, n1; Data(){} Data(int n1000, int n100, int n1): n1000(n1000), n100(n100), n1(n1){} bool operator< (const Data &opp) const { if (n1000 != opp.n1000) return n1000 < opp.n1000; if (n100 != opp.n100) return n100 < opp.n100; return n1 < opp.n1; } }; Data init; int payA, chgN1000A, chgN100A, chgN1A; int payB, chgN1000B, chgN100B, chgN1B; void read() { cin >> init.n1000 >> init.n100 >> init.n1; cin >> payA >> chgN1000A >> chgN100A >> chgN1A; cin >> payB >> chgN1000B >> chgN100B >> chgN1B; } Data doPay(int toPay, int chgN1000, int chgN100, int chgN1, Data curr) { int remain = toPay; int n; n = min(remain / 1000, curr.n1000); remain -= n * 1000; curr.n1000 -= n; n = min(remain / 100, curr.n100); remain -= n * 100; curr.n100 -= n; n = min(remain, curr.n1); remain -= n; curr.n1 -= n; if (remain == 0) return Data(curr.n1000 + chgN1000, curr.n100 + chgN100, curr.n1 + chgN1); else return Data(-1, -1, -1); } class mycmp { public: int operator()(const Data &a, const Data &b) const { return (b.n1000 * 1000 + b.n100 * 100 + b.n1) - (a.n1000 * 1000 + a.n100 * 100 + a.n1); } }; void work() { priority_queue, mycmp> Q; map d2cnt; Q.push(init); d2cnt[init] = 0; while (!Q.empty()) { Data curr = Q.top(); Q.pop(); Data next; // A next = doPay(payA, chgN1000A, chgN100A, chgN1A, curr); if (next.n1000 != -1) { if (!d2cnt.count(next) || d2cnt[next] < d2cnt[curr] + 1) { d2cnt[next] = d2cnt[curr] + 1; Q.push(next); } } // B next = doPay(payB, chgN1000B, chgN100B, chgN1B, curr); if (next.n1000 != -1) { if (!d2cnt.count(next) || d2cnt[next] < d2cnt[curr] + 1) { d2cnt[next] = d2cnt[curr] + 1; Q.push(next); } } } int ans = 0; for (map::iterator it = d2cnt.begin(); it != d2cnt.end(); ++it) ans = max(ans, it->second); cout << ans << endl; } int main() { read(); work(); return 0; }