#include #include #include #include #include #include #include using namespace std; using uint64 = unsigned long long; #define rep(i, n) for (int i = 0; i < int(n); ++i) constexpr int ipow(int base, int e, int res = 1) { return e == 0 ? res : (e & 1) ? ipow(base * base, e / 2, res * base) : ipow(base * base, e / 2, res); } using Pair = pair; Pair operator + (const Pair& lhs, const Pair& rhs) { return Pair(lhs.first + rhs.first, lhs.second + rhs.second); } // precision ... Pair operator - (const Pair& lhs, const Pair& rhs) { return Pair(lhs.first - rhs.first, lhs.second - rhs.second); } Pair& operator += (Pair& lhs, const Pair& rhs) { return lhs = lhs + rhs; } constexpr int N = 11; constexpr int three_N = ipow(3, N); double P[N][N]; int S[N][N]; Pair dp[2][1 << N]; Pair cumu[three_N]; int offsets[1 << N]; template void arith_transform_plus(T* A, int lvn) { int n = 1 << lvn; reverse(A, A + n); for (int lvm = lvn; lvm > 0; --lvm) { int m = 1 << lvm; int mh = m >> 1; for (int r = 0; r < n; r += m) rep(j, mh) A[r + j] += A[r + mh + j]; } } template void sum(T* A, int lv, T* res) { int total = 1 << lv; int pos = 0; rep (i, total) { res[pos++] = A[i]; int f = i; int t = 1; while (f) { int r = f & -f; int ofs = offsets[i ^ r]; rep(j, t) res[pos + j] = res[ofs + j] - res[pos - t + j]; pos += t; t <<= 1; f ^= r; } } } int ctz(int n) { return __builtin_ctz(n); } int pop_count(int n) { return __builtin_popcount(n); } int main() { int R, C; scanf("%d %d", &R, &C); int r; rep(i, R) rep(j, C) scanf("%d", &r), P[i][j] = r / 100.; rep(i, R) rep(j, C) scanf("%d", &S[i][j]), S[i][j] = 4 - S[i][j]; int total = 1 << C; int ofs = 0; rep(i, total) offsets[i] = ofs, ofs += 1 << pop_count(i); auto* curr = dp[0], *next = dp[1]; fill(curr, curr + total, Pair(0, 0)); curr[0] = Pair(0., 1.); arith_transform_plus(curr, C); sum(curr, C, cumu); rep(y, R) { fill(next, next + total, Pair(0, 0)); rep(s2, total) { double p = 1.0; rep(x, C) p *= (s2 & (1 << x)) ? P[y][x] : 1. - P[y][x]; if (p == 0) continue; auto s1 = s2; int ofs = offsets[s1] + (1 << pop_count(s2)) - 1; int points_back[N] = {}; int points[N]; rep(x, C) if (s2 & (1 << x)) points_back[x] = S[y][x]; do { if (cumu[ofs].second) { copy(points_back, points_back + C, points); auto s = s1; while (s) { auto t = s & -s; points[ctz(t)] += 1; s ^= t; } for (int x = 0; x < C - 1; ++x) if (points[x] >= 4) points[x + 1] += 1; for (int x = C - 1; x > 0; --x) if (points[x] >= 4) points[x - 1] += 1; int nstate = 0; rep(x, C) if (points[x] >= 4) { nstate |= 1 << x; } next[nstate] += Pair(p * (cumu[ofs].first + pop_count(nstate) * cumu[ofs].second), p * cumu[ofs].second); } s1 = (s1 - 1) & s2; ofs -= 1; } while (s1 != s2); } swap(curr, next); arith_transform_plus(curr, C); sum(curr, C, cumu); } printf("%.12f\n", cumu[0].first); return 0; }