#pragma GCC optimize("Ofast,no-stack-protector") #include <cstdio> #include <iostream> #include <iterator> #include <tr2/dynamic_bitset> #include <vector> using namespace std; using i64 = long long; constexpr int INF = 0x3f3f3f3f; int n, mn = INF; vector<int> curr, ans; tr2::dynamic_bitset<> vis; vector<vector<int>> times, magic; void solve(int mana, int lst = -1, int rnd = 0) { if (mana < 0 || rnd > mn) return; else if (ssize(curr) >= 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 ? times[lst][i] : 0)); curr.pop_back(); vis[i] = false; } } int main() { int m; scanf("%d %d", &n, &m); times.resize(n); magic.resize(n); vis.resize(n); curr.reserve(n); for (auto& row : times) { row.resize(n); for (int& x : row) cin >> x; } for (auto& row : magic) { row.resize(n); for (int& x : row) cin >> x; } solve(m); if (ans.empty()) puts("-1"); else { printf("%d\n", mn); for (int x : ans) printf("%d ", x + 1); } return 0; }