#pragma GCC optimize("Ofast,no-stack-protector") #include <cstdio> #include <tr2/dynamic_bitset> #include <vector> using namespace std; using i64 = long long; constexpr int INF = 0x3f3f3f3f; struct IO { #define MAXSIZE (1 << 20) #define isdigit(X) ((X) >= '0' && (X) <= '9') char buf[MAXSIZE], *p1, *p2; char pbuf[MAXSIZE], *pp; IO() : p1(buf) , p2(buf) , pp(pbuf) { } ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); } char getc() { if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin); return p1 == p2 ? ' ' : *p1++; } bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; } template <class T> void read(T& x) { double tmp = 1; bool sign = false; x = 0; char ch = getc(); for (; !isdigit(ch); ch = getc()) { if (ch == '-') sign = 1; } for (; isdigit(ch); ch = getc()) x = x * 10 + (ch - '0'); if (ch == '.') { for (ch = getc(); isdigit(ch); ch = getc()) { tmp /= 10.0; x += tmp * (ch - '0'); } } if (sign) x = -x; } void read(char* s) { char ch = getc(); for (; blank(ch); ch = getc()) ; for (; !blank(ch); ch = getc()) *s++ = ch; *s = 0; } void read(char& c) { for (c = getc(); blank(c); c = getc()) ; } template <class... T> void read(T&... vals) { (..., read(vals)); } void push(char c) { if (pp - pbuf == MAXSIZE) { fwrite(pbuf, 1, MAXSIZE, stdout); pp = pbuf; } *pp++ = c; } template <class T> void write(T x) { if (x < 0) { x = -x; push('-'); } static T sta[35]; T top = 0; do { sta[top++] = x % 10; x /= 10; } while (x); while (top) push(sta[--top] + '0'); } template <class T> void write(T x, char lst_ch) { write(x); push(lst_ch); } } io; int n, mn = INF; vector<int> curr, ans; tr2::dynamic_bitset<> vis; vector<vector<int>> round, magic; void solve(int mana, int lst = -1, int rnd = 0) { if (mana < 0 || rnd > mn) return; else if (curr.size() >= n) { if (mn > rnd) { mn = rnd; ans = curr; } return; } for (int i = 0; i < n; ++i) { if (vis[i]) continue; vis[i] = true; curr.emplace_back(i); solve(mana - (lst != -1 ? magic[lst][i] : 0), i, rnd + (lst != -1 ? round[lst][i] : 0)); curr.pop_back(); vis[i] = false; } } int main() { int m; io.read(n, m); round.resize(n); magic.resize(n); vis.resize(n); curr.reserve(n); for (auto& row : round) { row.resize(n); for (int& x : row) io.read(x); } for (auto& row : magic) { row.resize(n); for (int& x : row) io.read(x); } solve(m); if (ans.empty()) puts("-1"); else { io.write(mn, '\n'); for (int x : ans) io.write(x + 1, ' '); } return 0; }