#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__) #define debugv(v) {printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } mt19937 mt(8901016); inline int rand_int(int l, int h) { return uniform_int_distribution<>(l, h)(mt); } #ifdef __MAI #define getchar_unlocked getchar #define putchar_unlocked putchar #endif #ifdef __VSCC #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #endif namespace { #define isvisiablechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiablechar(cc); cc = getchar_unlocked()); for (; isvisiablechar(cc); cc = getchar_unlocked()) var.push_back(cc); } template void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; } }; } MaiScanner scanner; int n, len; int result = -1; ll a4, a3, a1; ll db, b4, b3, b1; ll dc, c4, c3, c1; map,ll> dp; // 1円玉の枚数は最大数だけ覚えておけば良い! /* my-testcase 2 0 0 1000 0 9 10 1000 0 8 90 */ int main() { scanner >> a4 >> a3 >> a1; scanner >> db; scanner >> b4 >> b3 >> b1; scanner >> dc; scanner >> c4 >> c3 >> c1; dp[make_pair(a4, a3)] = a1; int count = -1; bool updated = true; for (; updated; ++count) { updated = false; int next = (count + 1) % 2; int curr = (count) % 2; map, ll> dp_nxt; for (auto p : dp) { ll t1 = p.second; ll t4 = p.first.first; ll t3 = p.first.second; function dfs1 = [&](ll y, ll y4, ll y3, ll y1, ll x4, ll x3, ll x1, ll p4, ll p3, ll p1) { //xprintf("%lld %lld %lld %lld\n", y, x4, x3, x1); if (y % 100 > x1) return false; if ((y / 100) % 10 > x3) return 100 > x1 ? false : dfs1(y, y4, y3, y1, x4, x3 + 1, x1 - 100, p4, p3 - 1, p1 + 100); if ((y / 1000) % 10 > x4) return 10 > x3 ? (100 > x1 ? false : dfs1(y, y4, y3, y1, x4, x3 + 1, x1 - 100, p4, p3 - 1, p1 + 100)) : dfs1(y, y4, y3, y1, x4 + 1, x3 - 10, x1, p4 - 1, p3 + 10, p1); //xprintf("> %lld %lld %lld %lld\n", y, x4, x3, x1); ll o1 = y % 100 + p1; ll o3 = (y / 100)%10 + p3; ll o4 = (y / 1000)%10 + p4; auto key = make_pair(t4 - o4 + y4, t3 - o3 + y3); dp_nxt[key] = max(dp_nxt[key], t1 - o1 + y1); if (x3 >= 10) dfs1(y, y4, y3, y1, x4 + 1, x3 - 10, x1, p4 - 1, p3 + 10, p1); return true; }; updated |= dfs1(db, b4, b3, b1, t4, t3, t1, 0, 0, 0); updated |= dfs1(dc, c4, c3, c1, t4, t3, t1, 0, 0, 0); } dp.swap(dp_nxt); } cout << count << endl; return 0; }