// Marathon1.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <tchar.h>
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
#include "windows.h"
#include <process.h>
#include <algorithm>
#include <vector> 
#include <malloc.h>

#define WAIT_TIME 4965
#define bufferSize 20000
#define MAX_ELEMENTS 1001
#define  maxThreads  7
//#define MYDEBUG 1
//#define TOTALLIMIT 1

//unsigned short glValue[MAX_ELEMENTS*MAX_ELEMENTS];
//unsigned short glValueOrg[MAX_ELEMENTS*MAX_ELEMENTS];
unsigned short* glValue;
unsigned short* glValueOrg;
int glBestIdx[MAX_ELEMENTS];
int glBestTotal = 0;

unsigned long bestScore = 0;

#ifdef MYDEBUG
 int bestItemsStart = 0;
 int bestItemsStop  = 0;
 int bestItemsIter  = 0;
#endif

 #ifdef TOTALLIMIT
 int bestTotalItems = 0;
 #endif

int N = 0;
int OrgN = 0;
int M = 0;
unsigned short B = 0;
CRITICAL_SECTION glCS;

struct startInfo{
	int n;
	int k;
	int start;
	int stop;
};

struct scoreInfo{
	int idx;
	int score;
};

struct startPlan{
	int k;
	int start;
	int stop;
};

scoreInfo glScores[MAX_ELEMENTS];


clock_t begin_time = clock();

bool isRunning = true;
int glActiveThreads = 0;

template<unsigned char MyB, unsigned short MyM> 
unsigned int __stdcall bruteForce(void* mydata)
{
	unsigned short tempCalcs[MAX_ELEMENTS];
#ifdef TOTALLIMIT
	unsigned  long totalComb = 0;
#endif
	int i, j=1,*c, x;
	int z = 0;
	startInfo* info = (startInfo*)mydata;
	int n = info->n;
	int k = info->k;
	int start = info->start;
	int stop = info->stop;
	unsigned short * pInt;
	unsigned short * pIntSrc;
	unsigned  long tempTotalComb = 0;



	if (k==n) 	
	{
		glActiveThreads--;
		free(mydata);
		return 0;
	}


	c = (int*) malloc( (k+3) * sizeof(int));
 
	for (i=1; i <= k; ++i) c[i] = i;
	c[k+1] = n+1;
	c[k+2] = 0;
	j = k;
	if (start) {
		c[k] = start;
		j = 0;
	}
visit:
	if(stop>0 && c[k]>=stop){
#ifdef MYDEBUG
		printf("FORCE LIMIT %d -> Total time %dms (%u)\n",k, ( clock () - begin_time ),totalComb);
#endif
		goto imdone;
	}
	if (!isRunning) 
	{
#ifdef MYDEBUG
		printf("FORCE %d -> Total time %dms (%u)\n",k, ( clock () - begin_time ),totalComb);
#endif
		goto imdone;
	}

	//first row
	pIntSrc = glValue + (c[k]-1)*MyM;
	memcpy(tempCalcs, pIntSrc, MyM*sizeof(unsigned short));

	tempTotalComb = 0;
	for (i=k-1; i >= 2; --i) 
	{
		pIntSrc = glValue + (c[i]-1)*MyM;
		pInt = tempCalcs;
		for(z=0; z<MyM; ++z)  *pInt++ += *pIntSrc++;		
	}	

	//final row
	pIntSrc = glValue + (c[1]-1)*MyM;
	pInt = tempCalcs;
	for(z=0; z<MyM; ++z) 
	{
		unsigned short t = (*pInt++ + *pIntSrc++) % MyB;
		tempTotalComb += t*t;	

		//*pInt += *pIntSrc++;
		////while (*pInt>=MyB) *pInt-=MyB;
		//*pInt = *pInt % MyB;
		//tempTotalComb += *pInt**pInt;	
		//pInt++;
	}

	//!!!! CRITICAL SECTION BEG
	if (bestScore<tempTotalComb)
	{
		EnterCriticalSection(&glCS);
		#ifdef TOTALLIMIT
			bestTotalItems = k;
		#endif

		#ifdef MYDEBUG
			bestItemsStart = start;
			bestItemsStop = stop;
			bestItemsIter = totalComb;
		#endif		

		if (bestScore<tempTotalComb)
		{
			bestScore = tempTotalComb;
			glBestTotal = 0;
			for (i=k; i >= 1; --i) {
				glBestIdx[glBestTotal++]=c[i];
			}		
		}
		LeaveCriticalSection(&glCS);
	}
	//!!!! CRITICAL SECTION END

#ifdef TOTALLIMIT
	totalComb++;
	//if (MyM == 1000) if (totalComb>100000 && k<bestTotalItems) goto imdone;
	//if (MyM == 1000) if (totalComb>500000) goto imdone;
	//if (MyM == 200) if (totalComb>500000) goto imdone;
	//if (MyM == 1000) if (totalComb>1500000) goto imdone;
#endif
	if (j > 0) {x = j+1; goto incr;}
	if (c[1] + 1 < c[2])
	 {
	 c[1] += 1;
	 goto visit;
	 }
	j = 2;
do_more:
	c[j-1] = j-1;
	x = c[j] + 1;
	if (x == c[j+1]) {j++; goto do_more;}
	if (j > k) goto imdone;
incr:
	c[j] = x;
	j--;
	goto visit;
	
	
imdone:
#ifdef MYDEBUG
	printf("%d -> Total time %dms (%u)\n",k, ( clock () - begin_time ),totalComb);
#endif
	free(c); 
	free(mydata);
	glActiveThreads--;
	return 0;
}

bool acompare(scoreInfo a, scoreInfo b) 
{ 
	//return a.score < b.score; 
	return a.score > b.score; 
}


bool loadInput(char* fileName)
{
	char tempBuffer[bufferSize];


	FILE* in;
    char* next = NULL;
    char* c;
    int d;
    int idx;
	int i;
    
	in=fopen(fileName,"r");
	if (in==NULL) return false;
	
	if(fgets(tempBuffer,bufferSize,in))
    {
         sscanf(tempBuffer,"%d %d %d",&N,&M,&B);
		 OrgN = N;
    }
	//glValue = (unsigned short*)_aligned_malloc(N*M*sizeof(unsigned short*), 128);
	//glValueOrg = (unsigned short*)_aligned_malloc(N*M*sizeof(unsigned short*), 128);
	glValue = (unsigned short*)__mingw_aligned_malloc(N*M*sizeof(unsigned short), 128);
	glValueOrg = (unsigned short*)__mingw_aligned_malloc(N*M*sizeof(unsigned short), 128);

	//printf("N:%d, M:%d, B:%d\n",N,M,B);
	int totalRows = 0;

    for(i=0;i<N;++i){
		fgets(tempBuffer,bufferSize,in);
		c = tempBuffer;
		idx = 0;
		int start=i*M;
		unsigned int score = 0;
		do
		{
		  next = strstr(c," ");
		  if (next) next[0] = 0;
		  d = atoi(c);
		  c = next+1;
		  glValueOrg[start+idx] = d;

		  //glValue[start+idx] = d;
		  score += d;
		  idx++;
		}while(idx<M && next);
		


		if (score>0){
			//if (i%2) score = score*-1; //3rd place
			//score = score*-1; //2st place			
			glScores[totalRows].idx = i;
			glScores[totalRows].score = score;
			totalRows++;
		}
		//printf("\n");
	}

	N=totalRows;

	std::sort(glScores, glScores+N, acompare);

	//int middle=N/2;
	// for(i=0;i<middle;i++){
	//	 std::swap(glScores[i],glScores[N-1-i]); //best
	// }

	// for(i=1;i<=middle;i+=2){
		// std::swap(glScores[i],glScores[N-i]);
	// }

	//for(i=0;i<N;i++){
	//	int srcIdx = glScores[i].idx * M;
	//	int destIdx = i*M;
	//	for(int k=0;k<M;k++)
	//	{
	//		glValue[destIdx+k] = glValueOrg[srcIdx+k];
	//	}
	//}


	for(i=0;i<N;++i){
		unsigned short* srcIdx = glValueOrg + glScores[i].idx * M;
		unsigned short* destIdx = glValue + i*M;
		for(int k=0;k<M;++k)
		{
			*destIdx++ = *srcIdx++;
		}
	}


	//for(i=0;i<N;i++){
	//	int srcIdx = glScores[i].idx * M;
	//	int destIdx = i*M;
	//	memcpy(glValue+destIdx, glValueOrg+srcIdx, M*sizeof(unsigned int));
	//}

	return true;
}


void saveResult()
{
	FILE* out;
    out = fopen("subsetselection.out","w");	
	fprintf(out,"%d\n",glBestTotal);
	for(int k=0; k<glBestTotal; k++)
	{
		fprintf(out,"%d\n",glScores[glBestIdx[k]-1].idx+1);
		//fprintf(out,"%d\n",glBestIdx[k]);
	}
    fclose(out);
}


void calcAll()
{
	unsigned short tempCalcs[MAX_ELEMENTS];
	unsigned  long tempTotalComb = 0;
	glBestTotal = 0;
	memset(tempCalcs,0,M*sizeof(unsigned short)); 
	for (int i=0; i<N; ++i) 
	{
		int rowIdx = i*M;
		tempTotalComb = 0;
		for(int z=0; z<M; ++z) 
		{
			unsigned short tmpVal = tempCalcs[z] + glValue[rowIdx+z];
			if (tmpVal>=B) tmpVal-=B;
			tempTotalComb += tmpVal*tmpVal;
		}		
		
		if (tempTotalComb>bestScore)
		{
			for(int z=0; z<M; ++z) 
			{
				unsigned int tmpVal = tempCalcs[z] + glValue[rowIdx+z];
				if (tmpVal>=B) tmpVal-=B;
				tempCalcs[z] = tmpVal;
			}
			bestScore = tempTotalComb;
			glBestIdx[glBestTotal]=i+1;
			glBestTotal++;			
		}
	}	
}

HANDLE startForceThread(void* si)
{
	if (M==20)
	{
		if (B==2) return (HANDLE)_beginthreadex(0,0, &bruteForce<2,20>, si, 0, NULL);
        else if (B==3) return (HANDLE)_beginthreadex(0,0, &bruteForce<3,20>, si, 0, NULL);
        else if (B==4) return (HANDLE)_beginthreadex(0,0, &bruteForce<4,20>, si, 0, NULL);
        else if (B==5) return (HANDLE)_beginthreadex(0,0, &bruteForce<5,20>, si, 0, NULL);
        else if (B==6) return (HANDLE)_beginthreadex(0,0, &bruteForce<6,20>, si, 0, NULL);
        else if (B==7) return (HANDLE)_beginthreadex(0,0, &bruteForce<7,20>, si, 0, NULL);
        else if (B==8) return (HANDLE)_beginthreadex(0,0, &bruteForce<8,20>, si, 0, NULL);
        else if (B==9) return (HANDLE)_beginthreadex(0,0, &bruteForce<9,20>, si, 0, NULL);
        else if (B==10) return (HANDLE)_beginthreadex(0,0, &bruteForce<10,20>, si, 0, NULL);
        else if (B==11) return (HANDLE)_beginthreadex(0,0, &bruteForce<11,20>, si, 0, NULL);
        else if (B==12) return (HANDLE)_beginthreadex(0,0, &bruteForce<12,20>, si, 0, NULL);
        else if (B==13) return (HANDLE)_beginthreadex(0,0, &bruteForce<13,20>, si, 0, NULL);
        else if (B==14) return (HANDLE)_beginthreadex(0,0, &bruteForce<14,20>, si, 0, NULL);
        else if (B==15) return (HANDLE)_beginthreadex(0,0, &bruteForce<15,20>, si, 0, NULL);
        else if (B==16) return (HANDLE)_beginthreadex(0,0, &bruteForce<16,20>, si, 0, NULL);
        else if (B==17) return (HANDLE)_beginthreadex(0,0, &bruteForce<17,20>, si, 0, NULL);
        else if (B==18) return (HANDLE)_beginthreadex(0,0, &bruteForce<18,20>, si, 0, NULL);
        else if (B==19) return (HANDLE)_beginthreadex(0,0, &bruteForce<19,20>, si, 0, NULL);
        else if (B==20) return (HANDLE)_beginthreadex(0,0, &bruteForce<20,20>, si, 0, NULL);
	}
	
	if (M==200)
	{
		if (B==2) return (HANDLE)_beginthreadex(0,0, &bruteForce<2,200>, si, 0, NULL);
        else if (B==3) return (HANDLE)_beginthreadex(0,0, &bruteForce<3,200>, si, 0, NULL);
        else if (B==4) return (HANDLE)_beginthreadex(0,0, &bruteForce<4,200>, si, 0, NULL);
        else if (B==5) return (HANDLE)_beginthreadex(0,0, &bruteForce<5,200>, si, 0, NULL);
        else if (B==6) return (HANDLE)_beginthreadex(0,0, &bruteForce<6,200>, si, 0, NULL);
        else if (B==7) return (HANDLE)_beginthreadex(0,0, &bruteForce<7,200>, si, 0, NULL);
        else if (B==8) return (HANDLE)_beginthreadex(0,0, &bruteForce<8,200>, si, 0, NULL);
        else if (B==9) return (HANDLE)_beginthreadex(0,0, &bruteForce<9,200>, si, 0, NULL);
        else if (B==10) return (HANDLE)_beginthreadex(0,0, &bruteForce<10,200>, si, 0, NULL);
        else if (B==11) return (HANDLE)_beginthreadex(0,0, &bruteForce<11,200>, si, 0, NULL);
        else if (B==12) return (HANDLE)_beginthreadex(0,0, &bruteForce<12,200>, si, 0, NULL);
        else if (B==13) return (HANDLE)_beginthreadex(0,0, &bruteForce<13,200>, si, 0, NULL);
        else if (B==14) return (HANDLE)_beginthreadex(0,0, &bruteForce<14,200>, si, 0, NULL);
        else if (B==15) return (HANDLE)_beginthreadex(0,0, &bruteForce<15,200>, si, 0, NULL);
        else if (B==16) return (HANDLE)_beginthreadex(0,0, &bruteForce<16,200>, si, 0, NULL);
        else if (B==17) return (HANDLE)_beginthreadex(0,0, &bruteForce<17,200>, si, 0, NULL);
        else if (B==18) return (HANDLE)_beginthreadex(0,0, &bruteForce<18,200>, si, 0, NULL);
        else if (B==19) return (HANDLE)_beginthreadex(0,0, &bruteForce<19,200>, si, 0, NULL);
        else if (B==20) return (HANDLE)_beginthreadex(0,0, &bruteForce<20,200>, si, 0, NULL);
        else if (B==21) return (HANDLE)_beginthreadex(0,0, &bruteForce<21,200>, si, 0, NULL);
        else if (B==22) return (HANDLE)_beginthreadex(0,0, &bruteForce<22,200>, si, 0, NULL);
        else if (B==23) return (HANDLE)_beginthreadex(0,0, &bruteForce<23,200>, si, 0, NULL);
        else if (B==24) return (HANDLE)_beginthreadex(0,0, &bruteForce<24,200>, si, 0, NULL);
        else if (B==25) return (HANDLE)_beginthreadex(0,0, &bruteForce<25,200>, si, 0, NULL);
        else if (B==26) return (HANDLE)_beginthreadex(0,0, &bruteForce<26,200>, si, 0, NULL);
        else if (B==27) return (HANDLE)_beginthreadex(0,0, &bruteForce<27,200>, si, 0, NULL);
        else if (B==28) return (HANDLE)_beginthreadex(0,0, &bruteForce<28,200>, si, 0, NULL);
        else if (B==29) return (HANDLE)_beginthreadex(0,0, &bruteForce<29,200>, si, 0, NULL);
        else if (B==30) return (HANDLE)_beginthreadex(0,0, &bruteForce<30,200>, si, 0, NULL);
        else if (B==31) return (HANDLE)_beginthreadex(0,0, &bruteForce<31,200>, si, 0, NULL);
        else if (B==32) return (HANDLE)_beginthreadex(0,0, &bruteForce<32,200>, si, 0, NULL);
        else if (B==33) return (HANDLE)_beginthreadex(0,0, &bruteForce<33,200>, si, 0, NULL);
        else if (B==34) return (HANDLE)_beginthreadex(0,0, &bruteForce<34,200>, si, 0, NULL);
        else if (B==35) return (HANDLE)_beginthreadex(0,0, &bruteForce<35,200>, si, 0, NULL);
        else if (B==36) return (HANDLE)_beginthreadex(0,0, &bruteForce<36,200>, si, 0, NULL);
        else if (B==37) return (HANDLE)_beginthreadex(0,0, &bruteForce<37,200>, si, 0, NULL);
        else if (B==38) return (HANDLE)_beginthreadex(0,0, &bruteForce<38,200>, si, 0, NULL);
        else if (B==39) return (HANDLE)_beginthreadex(0,0, &bruteForce<39,200>, si, 0, NULL);
        else if (B==40) return (HANDLE)_beginthreadex(0,0, &bruteForce<40,200>, si, 0, NULL);
        else if (B==41) return (HANDLE)_beginthreadex(0,0, &bruteForce<41,200>, si, 0, NULL);
        else if (B==42) return (HANDLE)_beginthreadex(0,0, &bruteForce<42,200>, si, 0, NULL);
        else if (B==43) return (HANDLE)_beginthreadex(0,0, &bruteForce<43,200>, si, 0, NULL);
        else if (B==44) return (HANDLE)_beginthreadex(0,0, &bruteForce<44,200>, si, 0, NULL);
        else if (B==45) return (HANDLE)_beginthreadex(0,0, &bruteForce<45,200>, si, 0, NULL);
        else if (B==46) return (HANDLE)_beginthreadex(0,0, &bruteForce<46,200>, si, 0, NULL);
        else if (B==47) return (HANDLE)_beginthreadex(0,0, &bruteForce<47,200>, si, 0, NULL);
        else if (B==48) return (HANDLE)_beginthreadex(0,0, &bruteForce<48,200>, si, 0, NULL);
        else if (B==49) return (HANDLE)_beginthreadex(0,0, &bruteForce<49,200>, si, 0, NULL);
        else if (B==50) return (HANDLE)_beginthreadex(0,0, &bruteForce<50,200>, si, 0, NULL);
        else if (B==51) return (HANDLE)_beginthreadex(0,0, &bruteForce<51,200>, si, 0, NULL);
        else if (B==52) return (HANDLE)_beginthreadex(0,0, &bruteForce<52,200>, si, 0, NULL);
        else if (B==53) return (HANDLE)_beginthreadex(0,0, &bruteForce<53,200>, si, 0, NULL);
        else if (B==54) return (HANDLE)_beginthreadex(0,0, &bruteForce<54,200>, si, 0, NULL);
        else if (B==55) return (HANDLE)_beginthreadex(0,0, &bruteForce<55,200>, si, 0, NULL);
        else if (B==56) return (HANDLE)_beginthreadex(0,0, &bruteForce<56,200>, si, 0, NULL);
        else if (B==57) return (HANDLE)_beginthreadex(0,0, &bruteForce<57,200>, si, 0, NULL);
        else if (B==58) return (HANDLE)_beginthreadex(0,0, &bruteForce<58,200>, si, 0, NULL);
        else if (B==59) return (HANDLE)_beginthreadex(0,0, &bruteForce<59,200>, si, 0, NULL);
        else if (B==60) return (HANDLE)_beginthreadex(0,0, &bruteForce<60,200>, si, 0, NULL);
        else if (B==61) return (HANDLE)_beginthreadex(0,0, &bruteForce<61,200>, si, 0, NULL);
        else if (B==62) return (HANDLE)_beginthreadex(0,0, &bruteForce<62,200>, si, 0, NULL);
        else if (B==63) return (HANDLE)_beginthreadex(0,0, &bruteForce<63,200>, si, 0, NULL);
        else if (B==64) return (HANDLE)_beginthreadex(0,0, &bruteForce<64,200>, si, 0, NULL);
        else if (B==65) return (HANDLE)_beginthreadex(0,0, &bruteForce<65,200>, si, 0, NULL);
        else if (B==66) return (HANDLE)_beginthreadex(0,0, &bruteForce<66,200>, si, 0, NULL);
        else if (B==67) return (HANDLE)_beginthreadex(0,0, &bruteForce<67,200>, si, 0, NULL);
        else if (B==68) return (HANDLE)_beginthreadex(0,0, &bruteForce<68,200>, si, 0, NULL);
        else if (B==69) return (HANDLE)_beginthreadex(0,0, &bruteForce<69,200>, si, 0, NULL);
        else if (B==70) return (HANDLE)_beginthreadex(0,0, &bruteForce<70,200>, si, 0, NULL);
        else if (B==71) return (HANDLE)_beginthreadex(0,0, &bruteForce<71,200>, si, 0, NULL);
        else if (B==72) return (HANDLE)_beginthreadex(0,0, &bruteForce<72,200>, si, 0, NULL);
        else if (B==73) return (HANDLE)_beginthreadex(0,0, &bruteForce<73,200>, si, 0, NULL);
        else if (B==74) return (HANDLE)_beginthreadex(0,0, &bruteForce<74,200>, si, 0, NULL);
        else if (B==75) return (HANDLE)_beginthreadex(0,0, &bruteForce<75,200>, si, 0, NULL);
        else if (B==76) return (HANDLE)_beginthreadex(0,0, &bruteForce<76,200>, si, 0, NULL);
        else if (B==77) return (HANDLE)_beginthreadex(0,0, &bruteForce<77,200>, si, 0, NULL);
        else if (B==78) return (HANDLE)_beginthreadex(0,0, &bruteForce<78,200>, si, 0, NULL);
        else if (B==79) return (HANDLE)_beginthreadex(0,0, &bruteForce<79,200>, si, 0, NULL);
        else if (B==80) return (HANDLE)_beginthreadex(0,0, &bruteForce<80,200>, si, 0, NULL);
        else if (B==81) return (HANDLE)_beginthreadex(0,0, &bruteForce<81,200>, si, 0, NULL);
        else if (B==82) return (HANDLE)_beginthreadex(0,0, &bruteForce<82,200>, si, 0, NULL);
        else if (B==83) return (HANDLE)_beginthreadex(0,0, &bruteForce<83,200>, si, 0, NULL);
        else if (B==84) return (HANDLE)_beginthreadex(0,0, &bruteForce<84,200>, si, 0, NULL);
        else if (B==85) return (HANDLE)_beginthreadex(0,0, &bruteForce<85,200>, si, 0, NULL);
        else if (B==86) return (HANDLE)_beginthreadex(0,0, &bruteForce<86,200>, si, 0, NULL);
        else if (B==87) return (HANDLE)_beginthreadex(0,0, &bruteForce<87,200>, si, 0, NULL);
        else if (B==88) return (HANDLE)_beginthreadex(0,0, &bruteForce<88,200>, si, 0, NULL);
        else if (B==89) return (HANDLE)_beginthreadex(0,0, &bruteForce<89,200>, si, 0, NULL);
        else if (B==90) return (HANDLE)_beginthreadex(0,0, &bruteForce<90,200>, si, 0, NULL);
        else if (B==91) return (HANDLE)_beginthreadex(0,0, &bruteForce<91,200>, si, 0, NULL);
        else if (B==92) return (HANDLE)_beginthreadex(0,0, &bruteForce<92,200>, si, 0, NULL);
        else if (B==93) return (HANDLE)_beginthreadex(0,0, &bruteForce<93,200>, si, 0, NULL);
        else if (B==94) return (HANDLE)_beginthreadex(0,0, &bruteForce<94,200>, si, 0, NULL);
        else if (B==95) return (HANDLE)_beginthreadex(0,0, &bruteForce<95,200>, si, 0, NULL);
        else if (B==96) return (HANDLE)_beginthreadex(0,0, &bruteForce<96,200>, si, 0, NULL);
        else if (B==97) return (HANDLE)_beginthreadex(0,0, &bruteForce<97,200>, si, 0, NULL);
        else if (B==98) return (HANDLE)_beginthreadex(0,0, &bruteForce<98,200>, si, 0, NULL);
        else if (B==99) return (HANDLE)_beginthreadex(0,0, &bruteForce<99,200>, si, 0, NULL);
        else if (B==100) return (HANDLE)_beginthreadex(0,0, &bruteForce<100,200>, si, 0, NULL);		
	}
	
	if (M==1000)
	{
		if (B==2) return (HANDLE)_beginthreadex(0,0, &bruteForce<2,1000>, si, 0, NULL);
        else if (B==3) return (HANDLE)_beginthreadex(0,0, &bruteForce<3,1000>, si, 0, NULL);
        else if (B==4) return (HANDLE)_beginthreadex(0,0, &bruteForce<4,1000>, si, 0, NULL);
        else if (B==5) return (HANDLE)_beginthreadex(0,0, &bruteForce<5,1000>, si, 0, NULL);
        else if (B==6) return (HANDLE)_beginthreadex(0,0, &bruteForce<6,1000>, si, 0, NULL);
        else if (B==7) return (HANDLE)_beginthreadex(0,0, &bruteForce<7,1000>, si, 0, NULL);
        else if (B==8) return (HANDLE)_beginthreadex(0,0, &bruteForce<8,1000>, si, 0, NULL);
        else if (B==9) return (HANDLE)_beginthreadex(0,0, &bruteForce<9,1000>, si, 0, NULL);
        else if (B==10) return (HANDLE)_beginthreadex(0,0, &bruteForce<10,1000>, si, 0, NULL);
        else if (B==11) return (HANDLE)_beginthreadex(0,0, &bruteForce<11,1000>, si, 0, NULL);
        else if (B==12) return (HANDLE)_beginthreadex(0,0, &bruteForce<12,1000>, si, 0, NULL);
        else if (B==13) return (HANDLE)_beginthreadex(0,0, &bruteForce<13,1000>, si, 0, NULL);
        else if (B==14) return (HANDLE)_beginthreadex(0,0, &bruteForce<14,1000>, si, 0, NULL);
        else if (B==15) return (HANDLE)_beginthreadex(0,0, &bruteForce<15,1000>, si, 0, NULL);
        else if (B==16) return (HANDLE)_beginthreadex(0,0, &bruteForce<16,1000>, si, 0, NULL);
        else if (B==17) return (HANDLE)_beginthreadex(0,0, &bruteForce<17,1000>, si, 0, NULL);
        else if (B==18) return (HANDLE)_beginthreadex(0,0, &bruteForce<18,1000>, si, 0, NULL);
        else if (B==19) return (HANDLE)_beginthreadex(0,0, &bruteForce<19,1000>, si, 0, NULL);
        else if (B==20) return (HANDLE)_beginthreadex(0,0, &bruteForce<20,1000>, si, 0, NULL);
        else if (B==21) return (HANDLE)_beginthreadex(0,0, &bruteForce<21,1000>, si, 0, NULL);
        else if (B==22) return (HANDLE)_beginthreadex(0,0, &bruteForce<22,1000>, si, 0, NULL);
        else if (B==23) return (HANDLE)_beginthreadex(0,0, &bruteForce<23,1000>, si, 0, NULL);
        else if (B==24) return (HANDLE)_beginthreadex(0,0, &bruteForce<24,1000>, si, 0, NULL);
        else if (B==25) return (HANDLE)_beginthreadex(0,0, &bruteForce<25,1000>, si, 0, NULL);
        else if (B==26) return (HANDLE)_beginthreadex(0,0, &bruteForce<26,1000>, si, 0, NULL);
        else if (B==27) return (HANDLE)_beginthreadex(0,0, &bruteForce<27,1000>, si, 0, NULL);
        else if (B==28) return (HANDLE)_beginthreadex(0,0, &bruteForce<28,1000>, si, 0, NULL);
        else if (B==29) return (HANDLE)_beginthreadex(0,0, &bruteForce<29,1000>, si, 0, NULL);
        else if (B==30) return (HANDLE)_beginthreadex(0,0, &bruteForce<30,1000>, si, 0, NULL);
        else if (B==31) return (HANDLE)_beginthreadex(0,0, &bruteForce<31,1000>, si, 0, NULL);
        else if (B==32) return (HANDLE)_beginthreadex(0,0, &bruteForce<32,1000>, si, 0, NULL);
        else if (B==33) return (HANDLE)_beginthreadex(0,0, &bruteForce<33,1000>, si, 0, NULL);
        else if (B==34) return (HANDLE)_beginthreadex(0,0, &bruteForce<34,1000>, si, 0, NULL);
        else if (B==35) return (HANDLE)_beginthreadex(0,0, &bruteForce<35,1000>, si, 0, NULL);
        else if (B==36) return (HANDLE)_beginthreadex(0,0, &bruteForce<36,1000>, si, 0, NULL);
        else if (B==37) return (HANDLE)_beginthreadex(0,0, &bruteForce<37,1000>, si, 0, NULL);
        else if (B==38) return (HANDLE)_beginthreadex(0,0, &bruteForce<38,1000>, si, 0, NULL);
        else if (B==39) return (HANDLE)_beginthreadex(0,0, &bruteForce<39,1000>, si, 0, NULL);
        else if (B==40) return (HANDLE)_beginthreadex(0,0, &bruteForce<40,1000>, si, 0, NULL);
        else if (B==41) return (HANDLE)_beginthreadex(0,0, &bruteForce<41,1000>, si, 0, NULL);
        else if (B==42) return (HANDLE)_beginthreadex(0,0, &bruteForce<42,1000>, si, 0, NULL);
        else if (B==43) return (HANDLE)_beginthreadex(0,0, &bruteForce<43,1000>, si, 0, NULL);
        else if (B==44) return (HANDLE)_beginthreadex(0,0, &bruteForce<44,1000>, si, 0, NULL);
        else if (B==45) return (HANDLE)_beginthreadex(0,0, &bruteForce<45,1000>, si, 0, NULL);
        else if (B==46) return (HANDLE)_beginthreadex(0,0, &bruteForce<46,1000>, si, 0, NULL);
        else if (B==47) return (HANDLE)_beginthreadex(0,0, &bruteForce<47,1000>, si, 0, NULL);
        else if (B==48) return (HANDLE)_beginthreadex(0,0, &bruteForce<48,1000>, si, 0, NULL);
        else if (B==49) return (HANDLE)_beginthreadex(0,0, &bruteForce<49,1000>, si, 0, NULL);
        else if (B==50) return (HANDLE)_beginthreadex(0,0, &bruteForce<50,1000>, si, 0, NULL);
        else if (B==51) return (HANDLE)_beginthreadex(0,0, &bruteForce<51,1000>, si, 0, NULL);
        else if (B==52) return (HANDLE)_beginthreadex(0,0, &bruteForce<52,1000>, si, 0, NULL);
        else if (B==53) return (HANDLE)_beginthreadex(0,0, &bruteForce<53,1000>, si, 0, NULL);
        else if (B==54) return (HANDLE)_beginthreadex(0,0, &bruteForce<54,1000>, si, 0, NULL);
        else if (B==55) return (HANDLE)_beginthreadex(0,0, &bruteForce<55,1000>, si, 0, NULL);
        else if (B==56) return (HANDLE)_beginthreadex(0,0, &bruteForce<56,1000>, si, 0, NULL);
        else if (B==57) return (HANDLE)_beginthreadex(0,0, &bruteForce<57,1000>, si, 0, NULL);
        else if (B==58) return (HANDLE)_beginthreadex(0,0, &bruteForce<58,1000>, si, 0, NULL);
        else if (B==59) return (HANDLE)_beginthreadex(0,0, &bruteForce<59,1000>, si, 0, NULL);
        else if (B==60) return (HANDLE)_beginthreadex(0,0, &bruteForce<60,1000>, si, 0, NULL);
        else if (B==61) return (HANDLE)_beginthreadex(0,0, &bruteForce<61,1000>, si, 0, NULL);
        else if (B==62) return (HANDLE)_beginthreadex(0,0, &bruteForce<62,1000>, si, 0, NULL);
        else if (B==63) return (HANDLE)_beginthreadex(0,0, &bruteForce<63,1000>, si, 0, NULL);
        else if (B==64) return (HANDLE)_beginthreadex(0,0, &bruteForce<64,1000>, si, 0, NULL);
        else if (B==65) return (HANDLE)_beginthreadex(0,0, &bruteForce<65,1000>, si, 0, NULL);
        else if (B==66) return (HANDLE)_beginthreadex(0,0, &bruteForce<66,1000>, si, 0, NULL);
        else if (B==67) return (HANDLE)_beginthreadex(0,0, &bruteForce<67,1000>, si, 0, NULL);
        else if (B==68) return (HANDLE)_beginthreadex(0,0, &bruteForce<68,1000>, si, 0, NULL);
        else if (B==69) return (HANDLE)_beginthreadex(0,0, &bruteForce<69,1000>, si, 0, NULL);
        else if (B==70) return (HANDLE)_beginthreadex(0,0, &bruteForce<70,1000>, si, 0, NULL);
        else if (B==71) return (HANDLE)_beginthreadex(0,0, &bruteForce<71,1000>, si, 0, NULL);
        else if (B==72) return (HANDLE)_beginthreadex(0,0, &bruteForce<72,1000>, si, 0, NULL);
        else if (B==73) return (HANDLE)_beginthreadex(0,0, &bruteForce<73,1000>, si, 0, NULL);
        else if (B==74) return (HANDLE)_beginthreadex(0,0, &bruteForce<74,1000>, si, 0, NULL);
        else if (B==75) return (HANDLE)_beginthreadex(0,0, &bruteForce<75,1000>, si, 0, NULL);
        else if (B==76) return (HANDLE)_beginthreadex(0,0, &bruteForce<76,1000>, si, 0, NULL);
        else if (B==77) return (HANDLE)_beginthreadex(0,0, &bruteForce<77,1000>, si, 0, NULL);
        else if (B==78) return (HANDLE)_beginthreadex(0,0, &bruteForce<78,1000>, si, 0, NULL);
        else if (B==79) return (HANDLE)_beginthreadex(0,0, &bruteForce<79,1000>, si, 0, NULL);
        else if (B==80) return (HANDLE)_beginthreadex(0,0, &bruteForce<80,1000>, si, 0, NULL);
        else if (B==81) return (HANDLE)_beginthreadex(0,0, &bruteForce<81,1000>, si, 0, NULL);
        else if (B==82) return (HANDLE)_beginthreadex(0,0, &bruteForce<82,1000>, si, 0, NULL);
        else if (B==83) return (HANDLE)_beginthreadex(0,0, &bruteForce<83,1000>, si, 0, NULL);
        else if (B==84) return (HANDLE)_beginthreadex(0,0, &bruteForce<84,1000>, si, 0, NULL);
        else if (B==85) return (HANDLE)_beginthreadex(0,0, &bruteForce<85,1000>, si, 0, NULL);
        else if (B==86) return (HANDLE)_beginthreadex(0,0, &bruteForce<86,1000>, si, 0, NULL);
        else if (B==87) return (HANDLE)_beginthreadex(0,0, &bruteForce<87,1000>, si, 0, NULL);
        else if (B==88) return (HANDLE)_beginthreadex(0,0, &bruteForce<88,1000>, si, 0, NULL);
        else if (B==89) return (HANDLE)_beginthreadex(0,0, &bruteForce<89,1000>, si, 0, NULL);
        else if (B==90) return (HANDLE)_beginthreadex(0,0, &bruteForce<90,1000>, si, 0, NULL);
        else if (B==91) return (HANDLE)_beginthreadex(0,0, &bruteForce<91,1000>, si, 0, NULL);
        else if (B==92) return (HANDLE)_beginthreadex(0,0, &bruteForce<92,1000>, si, 0, NULL);
        else if (B==93) return (HANDLE)_beginthreadex(0,0, &bruteForce<93,1000>, si, 0, NULL);
        else if (B==94) return (HANDLE)_beginthreadex(0,0, &bruteForce<94,1000>, si, 0, NULL);
        else if (B==95) return (HANDLE)_beginthreadex(0,0, &bruteForce<95,1000>, si, 0, NULL);
        else if (B==96) return (HANDLE)_beginthreadex(0,0, &bruteForce<96,1000>, si, 0, NULL);
        else if (B==97) return (HANDLE)_beginthreadex(0,0, &bruteForce<97,1000>, si, 0, NULL);
        else if (B==98) return (HANDLE)_beginthreadex(0,0, &bruteForce<98,1000>, si, 0, NULL);
        else if (B==99) return (HANDLE)_beginthreadex(0,0, &bruteForce<99,1000>, si, 0, NULL);
        else if (B==100) return (HANDLE)_beginthreadex(0,0, &bruteForce<100,1000>, si, 0, NULL);		
	}	
	return NULL;
}


int _tmain(int argc, _TCHAR* argv[])
{	
	//unsigned int M = 50;
 //   //long fact = 0xCCCD;
	//unsigned long long fact = 0x51EB851F;
 //   for(unsigned int i=0; i<100; i++) {
 //       unsigned int a1 = i/M;
	//	unsigned int a2 =(fact*i>>34);
 //       if (a1!=a2) printf("%d %d\n", a1,a2);
 //   }

	//(0xCCCD*i)>>18


	InitializeCriticalSection(&glCS);
	loadInput("subsetselection.in");
	#ifdef MYDEBUG
	printf("Load in %dms\n", ( clock () - begin_time ));
	#endif
	
	std::vector<startPlan> myPlan;

	for(int z=2;z<N;++z){
		if (N<200){
			startPlan sp;
			sp.start = 0;
			sp.stop = 0;
			sp.k=z;
			myPlan.push_back(sp);
		} else if (N==200){
			if (z<=3)
			{
				startPlan sp; 
				sp.start = 0; sp.stop = 0; sp.k=z; myPlan.push_back(sp);
				// if(z==1)
				// {
					// sp.start = 0; sp.stop = 0; sp.k=199; myPlan.push_back(sp);
					// sp.start = 0; sp.stop = 0; sp.k=198; myPlan.push_back(sp);
					// sp.start = 0; sp.stop = 0; sp.k=197; myPlan.push_back(sp);
				// }
			}else{
				startPlan sp;
				//sp.start = 0; sp.stop = 150; sp.k=z; myPlan.push_back(sp);
				//sp.start = 150; sp.stop = 170; sp.k=z; myPlan.push_back(sp);
				//sp.start = 170; sp.stop = 190; sp.k=z; myPlan.push_back(sp);
				//sp.start = 190; sp.stop = 0; sp.k=z; myPlan.push_back(sp);
				
				sp.start = 0; sp.stop = 170; sp.k=z; myPlan.push_back(sp);
				sp.start = 170; sp.stop = 0; sp.k=z; myPlan.push_back(sp);
			}
		} else if (N==1000){
			if (z<=2)
			{
				startPlan sp; 
				sp.start = 0; sp.stop = 0; sp.k=z; myPlan.push_back(sp);
				// if(z==1)
				// {
					// sp.start = 0; sp.stop = 0; sp.k=999; myPlan.push_back(sp);
					// sp.start = 0; sp.stop = 0; sp.k=998; myPlan.push_back(sp);
					// //sp.start = 0; sp.stop = 0; sp.k=997; myPlan.push_back(sp);
				// }				
			}else{
				startPlan sp;
				//sp.start = 0; sp.stop = 500; sp.k=z; myPlan.push_back(sp);
				//sp.start = 500; sp.stop = 700; sp.k=z; myPlan.push_back(sp);
				//sp.start = 700; sp.stop = 800; sp.k=z; myPlan.push_back(sp);
				//sp.start = 800; sp.stop = 900; sp.k=z; myPlan.push_back(sp);
				//sp.start = 900; sp.stop = 950; sp.k=z; myPlan.push_back(sp);
				//sp.start = 950; sp.stop = 0; sp.k=z; myPlan.push_back(sp);

				sp.start = 0; sp.stop = 700; sp.k=z; myPlan.push_back(sp);
				sp.start = 700; sp.stop = 900; sp.k=z; myPlan.push_back(sp);
				sp.start = 900; sp.stop = 0; sp.k=z; myPlan.push_back(sp);							

				
			}

		}
	}

	calcAll();
	
	isRunning = true;
	int total = 0;
	while(isRunning)
	{
		if (glActiveThreads<maxThreads)
		{
			if (total<myPlan.size()) 
			{
				startInfo* si = new startInfo();
				si->n=N;
				si->k = myPlan[total].k;
				si->start = myPlan[total].start;
				si->stop = myPlan[total].stop;
				startForceThread((void*)si);
				total++;
				glActiveThreads++;
			}
		} else{
			Sleep(1);
		}
		if (glActiveThreads <=0 && total>=myPlan.size()) { isRunning = false; break; }
		if (clock() - begin_time>WAIT_TIME) isRunning = false;
	}


	saveResult();

#ifdef MYDEBUG
	printf("Done in %dms\n", ( clock () - begin_time ));
	printf("Best score: %d\n", bestScore);
	printf("DBG: %d %d %d %d\n", bestTotalItems, bestItemsStart, bestItemsStop, bestItemsIter);
#endif
	DeleteCriticalSection(&glCS);	
	
}