CodeChef submission 131083 (C++ 4.0.0-8) plaintext list. Status: RE, problem JX, contest NOV09. By gmark (Mark Greve), 2009-11-11 14:56:03.
// Help the DJ
// Source: CodeChef November Algorithm Challenge
// CodeChef ID:
// Author: Mark Greve
 
#define LOCAL
#ifdef LOCAL
#include <dirent.h>
#include <fstream>
#endif
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
typedef vector<vector<int> > vvi;
 
// Global variables to store the current best answer
vector<int> REAL_ANS;
int BEST_SOL;
 
inline int sqr(int x) { return x*x; }
 
// FAST IO
//{{{
// FAST IO
char *start;
const int MAXBUF=40000000;
char buf[MAXBUF];
int bufsz;
void take_input() {
	bufsz=fread(buf, sizeof(char), MAXBUF-1, stdin);
	buf[bufsz]='\0';
	start=buf;
}
void skip() { while (*start != '.' && !isdigit(*start)) ++start; }
void GETNUM(int& n){
	skip();
	n=0;
	while (isdigit(*start)) n = n*10 + *start-'0', ++start;
}
// END FAST IO
//}}}
 
// Evaluating a solution
//{{{
int eval_solution(const vvi& v, const vector<int>& sol) {
	if (sol.empty()) {
		return 0;
	}
 
	int ndancers = v.size()-1;
	int nsongs =  v[0].size()-1;
 
	vector<bool> covered(ndancers,0);
	vector<int> bored(ndancers);
	for (int i=0;i<ndancers;++i) bored[i] = v[i][nsongs];
 
	int ans = 0;
	for (int i=0;i<sol.size();++i) {
		int cursong = sol[i];
		for (int j=0;j<ndancers;++j) {
			if (v[j][cursong]) {
				if (!covered[j] && bored[j]>0) {
					covered[j] = 1;
					++ans;
				}
			}
			else {
				--bored[j];
				if (covered[j] && bored[j]==0) {
					--ans;
				}
			}
		}
	}
	return ans;
}
//}}}
 
// GREEDY WITH BACKTRACKING
//{{{
const int GMAX=501;
int G_bored[GMAX];
int G_ans;
int G_covered[GMAX];
int G_ndancers;
int G_nsongs;
int G_selected[GMAX];
int G_MAXITS;
int G_countones[GMAX];
int G_outbored;
int G_contained_in[GMAX];
bool G_chosen[GMAX];
 
void setup_greedy_backtracking(const vvi& v, int iterations) {
	G_MAXITS = iterations;
	G_ndancers = v.size()-1;
	G_nsongs =  v[0].size()-1;
	G_outbored = 0;
 
	if (BEST_SOL == G_ndancers) {
		G_MAXITS=0;
		return;
	}
 
	for (int i=0;i<G_nsongs;++i) {
		G_chosen[i] = 0;
	}
 
	for (int i=0;i<G_ndancers;++i) {
		G_bored[i] = v[i][G_nsongs];
		G_covered[i] = 0;
		G_contained_in[i] = 0;
	}
 
	for (int j=0;j<G_ndancers;++j) {
		for (int i=0;i<G_nsongs;++i) {
			if (v[j][i]) {
				++G_contained_in[j];
			}
		}
	}
 
	G_ans = 0;
}
void greedy_with_backtracking2(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (G_ndancers - G_outbored <= BEST_SOL) return;
	//printf("AT: %d, G_ANS %d G_OUT %d G_NDAN %d BEST %d\n", at, G_ans, G_outbored, G_ndancers, BEST_SOL);
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (!G_covered[j] && G_bored[j]>0) {
					num += 10000 + sqr(G_nsongs+1-G_contained_in[j]); 
				}
				else if (G_covered[j] && G_bored[j]>0) {
					num += 20;
				}
			}
			else {
				if (G_covered[j] && G_bored[j]==1) {
					num -= 10000;
				}
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>4) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				--G_contained_in[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking2(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				++G_contained_in[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking3(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (!G_covered[j] && G_bored[j]>0) {
					num += 1000000 + 40*(G_nsongs+1-G_contained_in[j]) + 41*sqr(G_nsongs - G_bored[j]);
				}
				else if (G_covered[j] && G_bored[j]>0) {
					num += 20;
				}
			}
			else {
				if (G_covered[j] && G_bored[j]==1) {
					num -= 1000000;
				}
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>4) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				--G_contained_in[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking3(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				++G_contained_in[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking4(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		//assert(0);
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (G_bored[j]>0) {
					if (!G_covered[j]) {
						if (G_bored[j]<=3) num += 100000;
						else num += 10;
					}
					else {
						if (G_bored[j]<=3) num += 10000;
						else ++num;
					}
				}
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) num -= 100000;
					else num -= 100000;
				}
				else if (G_bored[j]==2) num -= 10000;
				else if (G_bored[j]==3) num -= 1000;
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>10) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking4(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking5(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		//cerr << " GR 5 UPDATE TO " << G_ans << " vs " << BEST_SOL << endl;
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (at>=25) return;
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (!G_covered[j]) num += 40*(G_nsongs+1-G_contained_in[j]);
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) num -= 40*G_nsongs;
					else num -= 20*G_nsongs;
				}
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>7) { scores.erase(--scores.end()); }
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_contained_in[j];
				++G_covered[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking5(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_contained_in[j];
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking6(const vvi& v, int at) {
	//printf("G_ANS: %d, AT: %d, OUT: %d\n", G_ans,at, G_outbored);
	if (G_ans > BEST_SOL) { // Update to a better solution
		//cerr << "GR 6 UP TO " << G_ans << " prev " << BEST_SOL << endl;
		//assert(0);
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (at>=25) { return; }
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (!G_covered[j]) num += 100000;
					num += 40*sqr(G_nsongs+1-G_bored[j]);
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) num -= 100000;
						num -= 20*G_nsongs;
				}
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>4) { scores.erase(--scores.end()); }
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking6(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking7(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		//assert(0);
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (at>=25) {
		return;
	}
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (G_bored[j]>0) {
					if (!G_covered[j]) {
						if (G_bored[j]<=3) num += 100000;
						else num += 10;
					}
					else {
						if (G_bored[j]<=3) num += 10000;
						else ++num;
					}
				}
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) num -= 100000;
					else num -= 100000;
				}
				else if (G_bored[j]==2) num -= 10000;
				else if (G_bored[j]==3) num -= 1000;
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>4) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking7(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
void greedy_with_backtracking8(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		//cerr << "\tGREEDYBT 8: IMPROVE " << G_ans << endl;
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (at>=25) {
		return;
	}
	if (G_ndancers - G_outbored <= BEST_SOL) return;
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = 0;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				if (G_bored[j]>0) {
					if (!G_covered[j]) {
						if (G_bored[j]<=5) num += 100000;
						else num += 10;
					}
					else {
						if (G_bored[j]<=5) num += 10000;
						else ++num;
					}
				}
			}
			else {
				if (G_bored[j]==1) {
					num -= 100000;
				}
				else if (G_bored[j]==2) num -= 10000;
				else if (G_bored[j]==3) num -= 1000;
			}
		}
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>10) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking8(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
 
inline int score(const vvi& v, int z) {
	const int NDANCERS = v.size()-1;
	int num = 0;
	for (int j=0;j<NDANCERS;++j) {
		if (v[j][z]) {
			if (G_bored[j]>0) {
				if (!G_covered[j]) {
					if (G_bored[j]<=4) num += 100000;
					else num += 100000/5;
				}
				else {
					if (G_bored[j]<=4) num += 10000;
					else ++num;
				}
			}
		}
		else {
			if (G_bored[j]>0) {
				if (G_covered[j]) {
					if (G_bored[j]==1 || G_contained_in[j]==1) num -= 100000;
					else if (G_bored[j]==2 || G_contained_in[j]==2) num -= 2000;
					else if (G_bored[j]==3 || G_contained_in[j]==3) num -= 300;
				}
			}
		}
	}
	return num;
}
void greedy_with_backtracking10(const vvi& v, int at) {
	if (G_ans > BEST_SOL) { // Update to a better solution
		BEST_SOL = G_ans;
		REAL_ANS.clear();
		for (int i=0;i<at;++i) {
			REAL_ANS.push_back(G_selected[i]);
		}
		if (BEST_SOL == G_ndancers) {
			G_MAXITS = 0;
			return;
		}
	}
 
	if (at>=10) return;
	if (G_ndancers - G_outbored <= BEST_SOL) return;
	//printf("AT: %d, G_ANS %d G_OUT %d G_NDAN %d BEST %d\n", at, G_ans, G_outbored, G_ndancers, BEST_SOL);
 
	--G_MAXITS;
	if (G_MAXITS <= 0) return;
 
	set<pair<int,int > > scores;
	for (int z=0;z<G_nsongs && G_MAXITS > 0;++z) if (!G_chosen[z]) {
		int num = score(v,z);
		if (num > 0) {
			scores.insert(make_pair(-num,z));
			while (scores.size()>6) {
				scores.erase(--scores.end());
			}
		}
	}
 
	for (set<pair<int,int> >::iterator it = scores.begin(); it != scores.end(); ++it) {
		int z = it->second;
		int prev_ans = G_ans;
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_covered[j];
				--G_contained_in[j];
				if (G_covered[j]==1 && G_bored[j]>0) ++G_ans;
			}
			else {
				if (G_bored[j]==1) {
					if (G_covered[j]) {
						--G_ans;
					}
					++G_outbored;
				}
				--G_bored[j];
			}
		}
 
		if (G_ans>prev_ans) {
			G_chosen[z] = 1;
			G_selected[at] = z;
			greedy_with_backtracking10(v, at+1);
			G_chosen[z] = 0;
		}
 
		for (int j=0;j<G_ndancers;++j) {
			if (v[j][z]) {
				++G_contained_in[j];
				--G_covered[j];
				if (G_covered[j]==0 && G_bored[j]>0) --G_ans;
			}
			else {
				++G_bored[j];
				if (G_bored[j]==1) {
					if (G_covered[j]) ++G_ans;
					--G_outbored;
				}
			}
		}
	}
}
//}}}
// END GREEDY WITH BACKTRACKING
 
// GREEDY SET COVER SOLUTION
//{{{
	void greedy(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							//++num;
							num += /*v[j][nsongs]*/ + 10000 + (nsongs-contained_in[j]);
						}
						else if (covered[j] && bored[j]>0) {
							//num += 20;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							//--num;
							num -= 10000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 2
//{{{
	void greedy2(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							num += v[j][nsongs] + 10000;
						}
						else if (covered[j] && bored[j]>0) {
							num += 20;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							num -= 10000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY 2
 
// GREEDY SET COVER SOLUTION 3
//{{{
	void greedy3(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							num += 1000*(nsongs-bored[j]);
						}
						else if (covered[j] && bored[j]>0) {
							num += 5;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							num -= 1000*nsongs;
						}
						else if (bored[j]==1) {
							num -= 1000*nsongs;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY 3
 
// GREEDY SET COVER SOLUTION 4
//{{{
	void greedy4(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							//++num;
							num += 4*v[j][nsongs] + 10000 + 11*(nsongs-contained_in[j]);
						}
						else if (covered[j] && bored[j]>0) {
							num += 5;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							//--num;
							num -= 10000;
						}
						else if (bored[j]==1) {
							num -= 1000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 5
//{{{
	void greedy5(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							//++num;
							num += 7*v[j][nsongs] + 10000 + 30*(nsongs-contained_in[j]);
						}
						else if (covered[j] && bored[j]>0) {
							num += 10;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							//--num;
							num -= 10000;
						}
						else if (bored[j]==1) {
							num -= 5000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 6
//{{{
	void greedy6(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
			if (bored[i]<=5) bored[i]=0;
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							//++num;
							num += /*v[j][nsongs]*/ + 10000 + (nsongs-contained_in[j]);
						}
						else if (covered[j] && bored[j]>0) {
							//num += 20;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							//--num;
							num -= 10000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 7
//{{{
	void greedy7(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							//++num;
							num += 1000000 + 1000*(nsongs-contained_in[j]);
						}
						else if (covered[j] && bored[j]>0) {
							//num += 5;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							//--num;
							num -= 1000000;
						}
						else if (bored[j]==1) {
							num -= 500000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 8
//{{{
	void greedy8(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (bored[j]>0) {
							num += 1000*(nsongs-bored[j]);
						}
					}
					else {
						if (bored[j]>0) {
							num -= 1000*(nsongs-bored[j]);
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 9
//{{{
	void greedy9(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							num += sqr(sqr(nsongs-bored[j]));
						}
						else if (covered[j] && bored[j]>0) {
							num += 1;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							num -= 10000000;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// GREEDY SET COVER SOLUTION 10
//{{{
	void greedy10(const vvi& v) {
		if (BEST_SOL == v.size()-1)
			return;
 
		int ndancers = v.size()-1;
		int nsongs =  v[0].size()-1;
 
		vector<int> contained_in(ndancers,0);
		for (int j=0;j<ndancers;++j) {
			for (int i=0;i<nsongs;++i) {
				if (v[j][i]) {
					++contained_in[j];
				}
			}
		}
 
		vector<int> bored(ndancers);
		for (int i=0;i<ndancers;++i) {
			bored[i] = v[i][nsongs];
		}
 
		vector<int> choices;
		vector<int> covered(ndancers,0);
		vector<bool> chosen(nsongs,0);
 
		int curans = 0;
		int bestprefix = 0;
		int bestans = 0;
 
		while (1) {
			int choice = -1, best = 0;
			for (int i=0;i<nsongs;++i) if (!chosen[i]) {
				int num = 0;
				for (int j=0;j<ndancers && num!=-1;++j) {
					if (v[j][i]) {
						if (!covered[j] && bored[j]>0) {
							num += sqr(nsongs+1-bored[j]);
						}
						else if (covered[j] && bored[j]>0) {
							num += 1;
						}
					}
					else {
						if (covered[j] && bored[j]==1) {
							num = -1;
						}
						else if (bored[j]==1) {
							num = -1;
						}
					}
				}
 
				if (num > best || (num>=best && (rand()&1))) {
					choice = i;
					best = num;
				}
			}
			if (choice==-1) break;
 
			// Update for each dancer whether covered or not (and the boredom)
			for (int j=0;j<ndancers;++j) {
				if (v[j][choice]) {
					++covered[j];
					if (covered[j] == 1 && bored[j]>0) {
						++curans;
					}
				}
				else {
					--bored[j];
					if (bored[j]==0 && covered[j]) {
						--curans;
					}
				}
			}
 
			chosen[choice] = 1;
			choices.push_back(choice);
 
			if (curans > bestans) {
				bestans = curans;
				bestprefix = choices.size();
			}
		}
 
		if (bestans > BEST_SOL) {
			REAL_ANS = vector<int>(choices.begin(),choices.begin()+bestprefix);
			BEST_SOL = bestans;
		}
	}
//}}}
// END GREEDY
 
// BACKTRACKING
//{{{
const int MAX=501;
int B_bored[MAX];
int B_ans;
int B_covered[MAX];
int B_ndancers;
int B_nsongs;
int B_selected[MAX];
int B_MAXITS;
int B_countones[MAX];
int B_outbored;
 
void setup_backtracking(const vvi& v, int iterations) {
	B_MAXITS = iterations;
	B_ndancers = v.size()-1;
	B_nsongs =  v[0].size()-1;
	B_outbored = 0;
 
	if (BEST_SOL == B_ndancers) {
		B_MAXITS=0;
		return;
	}
 
	for (int i=0;i<B_ndancers;++i) {
		B_bored[i] = v[i][B_nsongs];
		B_covered[i] = 0;
	}
	B_ans = 0;
}
 
void backtrack(const vvi& v, int at, int i, int rem) {
	if (B_ans > BEST_SOL) { // Update to a better solution
		//printf("UPDATE TO %d\n", B_ans);
		BEST_SOL = B_ans;
		REAL_ANS.clear();
		for (int k=0;k<at;++k) {
			REAL_ANS.push_back(B_selected[k]);
		}
		if (BEST_SOL == B_ndancers) {
			B_MAXITS = 0;
			return;
		}
	}
 
	if (rem==0 || i >= B_nsongs) return;
	if (B_ndancers - B_outbored <= BEST_SOL) return;
 
	--B_MAXITS;
	if (B_MAXITS <= 0) return;
 
	int prev_ans = B_ans;
 
	for (int j=0;j<B_ndancers;++j) {
		if (v[j][i]) {
			++B_covered[j];
			if (B_covered[j]==1 && B_bored[j]>0) ++B_ans;
		}
		else {
			if (B_bored[j]==1) {
				if (B_covered[j]) --B_ans;
				++B_outbored;
			}
			--B_bored[j];
		}
	}
 
	if (B_ans > prev_ans) {
		B_selected[at] = i;
		backtrack(v, at+1, i+1,rem-1); 
	}
 
	for (int j=0;j<B_ndancers;++j) {
		if (v[j][i]) {
			--B_covered[j];
			if (B_covered[j]==0 && B_bored[j]>0) --B_ans;
		}
		else {
			++B_bored[j];
			if (B_bored[j]==1) {
				if (B_covered[j]) ++B_ans;
				--B_outbored;
			}
		}
	}
 
	backtrack(v, at, i+1,rem); 
}
//}}}
// END BACKTRACKING
 
// OPTIMIZE THE INSTANCE
//{{{
vvi delete_zero_rows(const vvi& v) {
	vvi ret;
	for (int i=0;i<v.size();++i) {
		bool allzero = 1;
		for (int j=0;j+1<v[i].size();++j) {
			if (v[i][j]!=0) { allzero = 0; break; }
		}
		if (!allzero) ret.push_back(v[i]);
	}
	return ret;
}
 
vvi transpose(const vvi& v) {
	vvi ret(v[0].size(),vector<int>(v.size()));
	for (int i=0;i<v.size();++i)
		for (int j=0;j<v[i].size();++j)
			ret[j][i] = v[i][j];
	return ret;
}
 
vvi remove_redundant_rows(const vvi& v) {
	vvi ret;
	int m = v.size()-1, n = v[0].size()-1;
 
	vector<vector<unsigned int> > bits(m);
	for (int i=0;i<m;++i) {
		for (int j=0;j<n;j+=32) {
			unsigned int cur = 0;
			for (int k=0;k<32 && j+k<n;++k) {
				if (v[i][j+k]==1) {
					cur |= (1u<<k);
				}
			}
			bits[i].push_back(cur);
		}
	}
 
	vector<bool> keep(m,1);
	for (int i=0;i<m;++i) if (keep[i]) {
		for (int j=i+1;j<m;++j) if (keep[j]) {
			bool kill = 1;
			for (int k=0;k<bits[i].size();++k) {
				if ( (bits[i][k] & bits[j][k]) != bits[j][k]) {
					kill = 0;
					break;
				}
			}
			if (kill) {
				keep[j] = 0;
			}
		}
	}
 
	for (int i=0;i<m;++i) if (keep[i]) {
		ret.push_back(v[i]);
	}
	ret.push_back(v.back());
	return ret;
}
 
template<class T> inline int BITCNT(T x){int r=0;while(x){r++;x&=x-1;}return r;}
 
vvi remove_redundant_rows_bounded2(const vvi& v) {
	cerr << "HEJ " << endl;
	vvi ret;
	int m = v.size()-1, n = v[0].size()-1;
 
	vector<vector<unsigned int> > bits(m);
	for (int i=0;i<m;++i) {
		for (int j=0;j<n;j+=32) {
			unsigned int cur = 0;
			for (int k=0;k<32 && j+k<n;++k) {
				if (v[i][j+k]==1) {
					cur |= (1u<<k);
				}
			}
			bits[i].push_back(cur);
		}
	}
 
	vector<bool> keep(m,1);
	for (int i=0;i<m;++i) if (keep[i]) {
		for (int j=i+1;j<m;++j) if (keep[j]) {
			int diff = 0;
			for (int k=0;k<bits[i].size() && diff <= 20;++k) {
				diff += BITCNT(bits[i][k] ^ bits[j][k]);
			}
			if (diff<=20) {
				assert(0);
				keep[j] = 0;
			}
		}
	}
 
	for (int i=0;i<m;++i) if (keep[i]) {
		ret.push_back(v[i]);
	}
	ret.push_back(v.back());
	return ret;
}
vvi remove_redundant_rows_bounded(const vvi& v, const int bound) {
	if (bound==-1) return remove_redundant_rows_bounded2(v);
	vvi ret;
	int m = v.size()-1, n = v[0].size()-1;
 
	vector<vector<unsigned int> > bits(m);
	for (int i=0;i<m;++i) {
		for (int j=0;j<n;j+=32) {
			unsigned int cur = 0;
			for (int k=0;k<32 && j+k<n;++k) {
				if (v[i][j+k]==1 && v[m][j+k] <= bound) {
					cur |= (1u<<k);
				}
			}
			bits[i].push_back(cur);
		}
	}
 
	vector<bool> keep(m,1);
	for (int i=0;i<m;++i) if (keep[i]) {
		for (int j=i+1;j<m;++j) if (keep[j]) {
			bool kill = 1;
			for (int k=0;k<bits[i].size();++k) {
				if ( (bits[i][k] & bits[j][k]) != bits[j][k]) {
					kill = 0;
					break;
				}
			}
			if (kill) {
				//cerr << "\t KILL " << j << " BOUND " << bound << endl;
				keep[j] = 0;
			}
		}
	}
 
	for (int i=0;i<m;++i) if (keep[i]) {
		ret.push_back(v[i]);
	}
	ret.push_back(v.back());
	return ret;
}
 
 
vvi remove_one_rows(const vvi& v) {
	int m = v.size()-1, n = v[0].size()-1;
	vector<bool> keep(m,1);
	for (int j=0;j<n;++j) if (v[m][j]==1) {
		for (int i=0;i<m;++i) if (v[i][j] == 0) {
			keep[i] = 0;
		}
	}
 
	vvi ret;
	for (int i=0;i<m;++i) if (keep[i]) {
		ret.push_back(v[i]);
	}
	ret.push_back(v.back());
	return ret;
}
//}}}
// END OPTIMIZE THE INSTANCE
 
// UTILITY FUNCTIONS
//{{{
int count_ones(const vector<int>& v) {
	int ans = 0;
	for (int i=0;i+1<v.size();++i) ans += v[i];
	return ans;
}
int rate(const vvi& v, int i) {
	int NSONGS = v.size()-1;
	int ans = 0;
	for (int j=0;j+1<v[i].size();++j) if (v[i][j] && v[NSONGS][j]>=15) {
		ans += 100000;
	}
	return ans;
}
void show(const vvi& v) {
	for (int i=0;i<v.size();++i) {
		for (int j=0;j<v[i].size();++j) {
			cerr << v[i][j] << " ";
		}
		cerr << endl;
	}
}
vvi remove_boredom_bound(const vvi& v, const int bound) {
	int m = v.size()-1, n = v[0].size()-1;
	vvi ret;
	for (int i=0;i<m;++i) if (v[i][n]>bound) ret.push_back(v[i]);
	ret.push_back(v.back());
	return ret;
}
//}}}
// END UTILITY FUNCTIONS
 
pair<int, vector<int> > realsolve(vvi& L, const int BOUND=1<<30) {
	int PREVANS = BEST_SOL;
 
	{ // Make some simple transformations on L
		L = delete_zero_rows(L);
		L = transpose(L);
		L = delete_zero_rows(L);
 
		{
			vector<pair<int,int> > ones_sort(L.size());
			for (int i=0;i+1<L.size();++i) {
				ones_sort[i] = make_pair(count_ones(L[i]),i);
			}
			sort(ones_sort.begin(),--ones_sort.end(),greater<pair<int,int> >());
 
			{
				vvi NL(L.size());
				for (int i=0;i<ones_sort.size();++i) {
					NL[i] = L[ones_sort[i].second];
				}
				NL.back() = L.back();
				L = NL;
			}
		}
 
		L = remove_redundant_rows_bounded(L, BOUND);
		L = transpose(L);
	}
 
	greedy(L);   greedy(L); greedy(L); greedy(L); greedy(L); greedy(L); greedy(L);
	greedy2(L);  greedy2(L);
	greedy3(L);  greedy3(L);
	greedy4(L);  greedy4(L);
	greedy5(L);  greedy5(L);
	greedy6(L);  greedy6(L);
	greedy7(L);  greedy7(L);
	greedy8(L);  greedy8(L);
	greedy9(L);  greedy9(L);
	greedy10(L); greedy10(L);
 
	{ // Do some greedy backtracking
		int NUMDANCERS = L.size()-1;
		int NUMSONGS = L[0].size()-1;
 
		setup_greedy_backtracking(L, 100000000/(6*NUMDANCERS*NUMSONGS));
		greedy_with_backtracking2(L,0);
 
		setup_greedy_backtracking(L, 100000000/(6*NUMDANCERS*NUMSONGS));
		greedy_with_backtracking8(L,0);
 
		/*
			 setup_greedy_backtracking(L, 100000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking10(L,0);
			 */
 
		/*
			 setup_greedy_backtracking(L, 100000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking3(L,0);
			 */
 
		/*
			 setup_greedy_backtracking(L, 200000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking4(L,0);
			 */
 
		/*
			 setup_greedy_backtracking(L, 200000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking5(L,0);
			 */
 
		/*
			 setup_greedy_backtracking(L, 200000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking6(L,0);
			 */
 
		/*
			 setup_greedy_backtracking(L, 200000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking7(L,0);
			 */
 
 
		/*
			 setup_greedy_backtracking(L, 100000000/(6*NUMDANCERS*NUMSONGS));
			 greedy_with_backtracking9(L,0, 0);
			 */
	}
 
	/*
		 {
		 int NUMDANCERS = L[0].size()-1;
	//setup_backtracking(L, 500000000/(6*NUMDANCERS));
	setup_backtracking(L, 1<<30);
	backtrack(L,0,0,25);
	}
	*/
 
done:
	if (BEST_SOL > PREVANS) {
		vector<int> ret(REAL_ANS.size());
		for (int i=0;i<REAL_ANS.size();++i) {
			ret[i] = L[L.size()-1][REAL_ANS[i]];
		}
		return make_pair(BEST_SOL, ret);
	}
	else {
		return make_pair(0, vector<int>());
	}
}
 
void do_output(const vector<int>& v) {
	assert(v.size()<=25);
	printf("%d\n", v.size());
	for (int i=0;i<v.size();++i) printf("%d\n", v[i]);
}
 
bool solve(bool output) {
	int D,S;
 
	GETNUM(D);
	GETNUM(S);
 
	vector<int> B(D);
	vvi L(D+1,vector<int>(S+1,0));
	for (int i=0;i<D;++i) {
		GETNUM(B[i]);
	}
 
	for (int i=0;i<D;++i) {
		for (int j=0;j<S;++j) {
			GETNUM(L[i][j]);
		}
		// Append the boredom for each dancer
		L[i][S] = B[i];
	}
	// Name of the songs as an extra row.
	for (int i=0;i<S;++i) {
		L[D][i] = i;
	}
 
	BEST_SOL = 0;
	REAL_ANS.clear();
	srand(time(NULL));
 
	pair<int,vector<int> > p0 = realsolve(L);
	if (L.size()-1 == p0.first) { // optimal solution
		if (output) do_output(p0.second);
		return 1;
	}
 
	vector<int>& ans = p0.second;
 
	const vvi copyL = L;
 
	if (L.size()-1 > BEST_SOL && L[0].size()>1) {
		int PREV_SOL = BEST_SOL;
		pair<int,vector<int> > p1 = realsolve(L,30);
#ifndef ONLINE_JUDGE
		cerr << "\t1: TRYING HERE " << L.size()-1 << " AND NSONGS " << L[0].size() - 1 << " GET " << BEST_SOL << " PREV " << PREV_SOL << endl;
#endif
		if (p1.first > PREV_SOL) {
#ifdef ONLINE_JUDGE
#endif
			ans = p1.second;
		}
	}
 
	if (L.size()-1 > BEST_SOL && L[0].size()>1) {
		L = copyL;
 
		int PREV_SOL = BEST_SOL;
		pair<int,vector<int> > p2 = realsolve(L,-1);
#ifndef ONLINE_JUDGE
		cerr << "\t2: TRYING HERE " << L.size()-1 << " AND NSONGS " << L[0].size() - 1 << " GET " << BEST_SOL << " PREV " << PREV_SOL << endl;
#endif
		if (p2.first > PREV_SOL) {
#ifdef ONLINE_JUDGE
			assert(0);
#endif
			ans = p2.second;
		}
	}
 
	if (output) do_output(ans);
	return 0;
 
	/*
		 { // Keep only songs for dancers with boredom one
		 const int NDANCERS = L.size()-1, NSONGS = L[0].size()-1;
		 cerr << "\t PREV NDANCERS " << L.size()-1 << " NSONGS " << L[0].size()-1 << endl;
		 vector<bool> keep(NSONGS,1);
 
		 vector<int> numb(NDANCERS,0);
		 for (int i=0;i<NDANCERS;++i) ++numb[L[i][NSONGS]];
 
		 for (int j=0;j<NSONGS;++j) {
		 for (int i=0;i<NDANCERS;++i) if (L[i][NSONGS]==1 && !L[i][j]) {
		 keep[j] = 0;
		 break;
		 }
		 }
 
		 int totb = 0;
		 const int CONS = 5;
		 for (int i=0;i<min(NDANCERS,CONS+1);++i) totb += numb[i];
 
		 for (int j=0;j<NSONGS;++j) {
		 int cnt = 0;
		 for (int i=0;i<NDANCERS;++i) if (L[i][NSONGS]<=5 && L[i][j]) {
		 ++cnt;
		 }
		 if (cnt>0 && cnt>=totb/2) {
		 keep[j] = 1;
		 }
		 }
 
		 L = transpose(L);
		 vvi newL;
		 for (int i=0;i<NSONGS;++i) if (keep[i]) newL.push_back(L[i]);
		 newL.push_back(L.back());
		 newL = transpose(newL);
		 L = newL;
		 cerr << "\t NOW NDANCERS " << L.size()-1 << " NSONGS " << L[0].size()-1 << endl;
 
		 if (NSONGS == L[0].size()-1) {
		 if (output) do_output(p0.second);
		 return 0;
		 }
		 }
		 */
 
 
 
	//vvi oldL = L;
 
	/*
	// Doesn't seem to have any effect
	L = oldL;
 
	int p0s = L.size(), p1s = L[0].size();
	for (int r=20,its=0;its<1;++r,++its) {
	L = remove_boredom_bound(L, r);
	if (L.size()-1 <= BEST_SOL || L[0].size()<=1) break;
 
	if (p0s == L.size() && p1s == L[0].size()) continue;
	p0s = L.size(), p1s = L[0].size();
 
	int PREV_SOL = BEST_SOL;
	pair<int,vector<int> > p2 = realsolve(L);
#ifndef ONLINE_JUDGE
cerr << "\t2: TRYING HERE " << L.size()-1 << " AND NSONGS " << L[0].size() - 1 << " GET " << BEST_SOL << " PREV " << PREV_SOL << endl;
#endif
if (p2.first > PREV_SOL) {
#ifdef ONLINE_JUDGE
assert(0);
#endif
ans = p2.second;
}
}
*/
 
	if (output) do_output(ans);
	return 0;
	}
 
// LOCAL TESTS
//{{{
#ifdef LOCAL
void run_tests() {
 
	int sol = 0;
	int opt_solve = 0;
	int tot = 0;
 
	string curdir = "testdata";
	DIR* dir = opendir(curdir.c_str());
	for (dirent* de; de = readdir(dir);) {
		if (!strcmp(de->d_name,".svn")) continue;
 
		if (de->d_type == DT_DIR) { // recurse into this directory
			continue;
		}
		else if (de->d_type == DT_REG) {
			string name = curdir + "/" + de->d_name;
			if (name.length()>=3 && name.substr(int(name.length())-4)==".txt") {
				ifstream fin(name.c_str());
				bufsz = 0;
				for (string x;getline(fin,x);) {
					for (int j=0;j<x.length();++j) {
						buf[bufsz++] = x[j];
					}
					buf[bufsz++] = '\n';
				}
				start = buf;
 
				int bestsolved = solve(false);
 
				cerr << "Case " << de->d_name << "\tsolved opt: " << bestsolved << "\tsolution " << BEST_SOL << " SIZE " << REAL_ANS.size() << endl;
 
				opt_solve += bestsolved;
				sol += BEST_SOL;
				++tot;
			}
		}
	}
	cerr << endl;
	cerr << "STATS     "  << endl;
	cerr << "SCORE   : " << sol << endl;
	cerr << "OPT SOL : " << opt_solve << endl;
	cerr << "NUM CAS : " << tot << endl;
	closedir(dir);
}
#endif
//}}}
// END LOCAL TESTS
 
int main(int argc, char** argv) {
	if (argc == 2 && !strcmp(argv[1], "tests")) {
#ifdef LOCAL
		cerr << "RUNNING TESTS " << endl;
		run_tests();
		return 0;
#endif
	}
	take_input();
	solve(true);
}