// yukicoder: No.158 奇妙なお使い // 2019.7.19 bal4u #include #include #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } int dp[10002][12][102]; int b1000, b100, b1; int enable(int a1000, int a100, int a1, int d) { if (d >= 1000 && a1000) { if (a1000 >= d/1000) a1000 -= d/1000, d %= 1000; else d -= a1000*1000, a1000 = 0; } if (d >= 100 && a100) { if (a100 >= d/100) a100 -= d/100, d %= 100; else d -= a100*100, a100 = 0; } if (a1 >= d) { b1000 = a1000, b100 = a100, b1 = a1 - d; return 1; } return 0; } #define TOTAL(a,b,c) ((a)*1000+(b)*100+(c)) int main() { int i, j, k, l, t, f, jma, kma; int a[3], d[2], b[2][3]; for (i = 0; i < 3; i++) a[i] = in(); for (i = 0; i < 2; i++) { d[i] = in(); for (j = 0; j < 3; j++) b[i][j] = in(); } // for special case for (i = 0; i < 2; i++) { if (d[i] - (j = TOTAL(b[i][0], b[i][1], b[i][2])) == 1 && d[i] <= d[!i]) { if (a[0] >= b[i][0] && a[0]*10+a[1] >= b[i][0]*10+b[i][1] && (k = TOTAL(a[0], a[1], a[2])) >= j) { printf("%d\n", k-j); return 0; } } } memset(dp, -1, sizeof(dp)); dp[0][jma=a[0]][kma=a[1]] = a[2], f = 1; for (i = 0; f; i++) { int jj = jma, kk = kma; jma = kma = 0, f = 0; for (j = 0; j <= jj; j++) for (k = 0; k <= kk; k++) if ((t = dp[i][j][k]) >= 0) { for (l = 0; l < 2; l++) if (enable(j, k, t, d[l])) { int *x = &(dp[i+1][b1000+b[l][0]][b100+b[l][1]]); f = 1; if (*x < b1+b[l][2]) *x = b1+b[l][2]; if (b1000+b[l][0] > jma) jma = b1000+b[l][0]; if (b100 +b[l][1] > kma) kma = b100 +b[l][1]; } } } printf("%d\n", i-1); return 0; }