#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N); for(int i = 0; i < N; ++i) cin >> A[i]; vector> B(N, vector(N)); for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ cin >> B[i][j]; } } vector> score(N, vector(1 << N)); for(int i = 0; i < N; ++i){ for(int mask = 0; mask < 1 << N; ++mask){ if(mask >> i & 1) continue; score[i][mask] += A[i]; for(int j = 0; j < N; ++j){ if(mask >> j & 1) score[i][mask] += B[i][j]; } } } constexpr ll inf = 1e+17; vector dp(1 << N, -inf); dp[0] = 0; for(int mask = 0; mask < 1 << N; ++mask){ for(int i = 0; i < N; ++i){ if(mask >> i & 1) continue; chmax(dp[mask | (1 << i)], dp[mask] + score[i][mask]); } } ll max_score = 0; int max_mask = 0; for(int mask = 0; mask < 1 << N; ++mask){ if(chmax(max_score, dp[mask])) max_mask = mask; } vector notes; for(int i = 0; i < N; ++i){ if(max_mask >> i & 1) notes.emplace_back(i + 1); } int n = notes.size(); cout << max_score << '\n'; for(int i = 0; i < n; ++i){ cout << notes[i] << (i == n - 1 ? '\n' : ' '); } return 0; }