#include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef vector VI; typedef vector VVI; typedef vector VVVI; typedef vector VL; #define FOR(k,a,b) for(int k(a); k < (b); ++k) #define FORD(k,a,b) for(int k(b-1); k >= (a); --k) #define REP(k,a) for(int k=0; k < (a); ++k) #define ABS(a) ((a)>0?(a):-(a)) #define EPS 1e-9 #define INF 1e9 int main(int argc, char** argv) { #ifdef HOME freopen("in.txt", "rb", stdin); freopen("out.txt", "wb", stdout); #endif int N, K,NNN, tmp; scanf("%d %d", &N, &K); NNN = N*N*N; VI D(NNN); REP(i, NNN) scanf("%d", &D[i]); int logN = log2(N) + 1; VVVI dp(logN); VVI c0(logN), c1(logN); tmp = NNN; REP(i, logN) { dp[i].resize(tmp); c0[i].resize(tmp); c1[i].resize(tmp); tmp /= 8; } REP(i, NNN) { if (D[i]) c1[0][i] = 1; else c0[0][i] = 1; } tmp = 1; REP(i, logN) { REP(j,dp[i].size()) dp[i][j].resize(tmp+1,INF); tmp *= 8; } tmp = N; REP(level, logN - 1) { REP(i, c0[level].size()) { int x = i % tmp; int y = (i / tmp) % tmp; int z = i / tmp / tmp; x /= 2, y /= 2, z /= 2; int ii = x + y * tmp / 2 + z * tmp * tmp / 4; c0[level + 1][ii] += c0[level][i]; c1[level + 1][ii] += c1[level][i]; } tmp /= 2; } //second level REP(j, dp[1].size()) { dp[1][j][1] = min(c0[1][j],c1[1][j]); dp[1][j][8] = dp[1][j][1]? 0 : 1; } //transition tmp = N / 2; FOR(level, 2, logN) { tmp /= 2; REP(i, dp[level].size()) { int x = i % tmp; int y = (i / tmp) % tmp; int z = i / tmp / tmp; int ii = 2 * x + 4 * y * tmp + 8 * z * tmp * tmp; REP(k, dp[level - 1][ii].size()) { dp[level][i][k] = dp[level - 1][ii][k]; } FOR(k,1, 8) { int kx = k & 1; int ky = (k & 2) >> 1; int kz = (k & 4 ) >> 2; ii = 2 * x + kx + 4 * y * tmp + ky * 2 * tmp + 8 * z * tmp * tmp + 4 * kz * tmp * tmp; const VI& vn = dp[level - 1][ii]; VI& va = dp[level][i]; VI nva(va.size(), INF); for (int j = va.size() - 1; j > -1; --j) if (va[j] != INF) { REP(o, vn.size()) if(vn[o] != INF) { int oj = o + j; int voj = va[j] + vn[o]; if (nva[oj] > voj) { nva[oj] = voj; } } } nva.swap(va); } //check if all equal, correction if (c0[level][i] * c1[level][i] == 0) { if (dp[level][i][8] == 0) dp[level][i][8] = 1; } int n1 = min(c0[level][i], c1[level][i]); dp[level][i][1] = n1; // } } const VI& f = dp[logN - 1][0]; int mi = INF, mx = 0; REP(i, f.size()) { if (f[i] <= K) { mi = min(mi, i); mx = max(mx, i); } } printf("%d %d\n", mi, mx); return 0; }