/*
TASK: KROKODILAIJ
LANG: C++
*/

#include <fstream>

#include <iostream>
using namespace std;

#define inputFile		"KROKOs02.DAT"
#define outputFile		"KROKO.REZ"

// kiek yra skirtingų agresyvių (arba neagresyvių) krokodilų
#define skirtingu	(1000000 + 1)
// maksimalus krokodilų skaičius
#define maks		3000000

// susumuojama distribucija, kad vienu kreipiniu į masyvą būtų galima rasti
// didesnių arba lygių už pasirinktą slenkstį elementų kiekį
void suma(int *sumos, int *distribucija, int viso)
{
	sumos[0] = 0;
	for (int t = 1; t < viso; ++t)
		sumos[t] = distribucija[t - 1] + sumos[t - 1];
}

// surandamas minimalus slenkstis, kuriuo agresyvūs krokodilai atskiriami
// nuo neagresyvių darant mažiausiai klaidų
int slenkstis(int *sumos, int *distribucija, int viso, int *klaida)
{
	int gerSlenkstis = -1;
	int klaidos = 0;
	
	*klaida = maks;
	for (int i = viso - 1; i >= 0; --i)
	{
		klaidos += distribucija[i];
		if (klaidos + sumos[i] <= *klaida)
		{
			//if (klaidos + sumos[i] < *klaida)
			//	cout << i << "\t" << klaidos + sumos[i] << endl;
			*klaida = klaidos + sumos[i];
			gerSlenkstis = i;
		}
	}

	return gerSlenkstis;
}

int main()
{
	int *agresyvus = new int[skirtingu];
	int *neagresyvus = new int[skirtingu];

	memset(agresyvus, 0, sizeof(int) * skirtingu);
	memset(neagresyvus, 0, sizeof(int) * skirtingu);

	// nuskaitome pradinius duomenis. uždaviniui išspręsti nereikia saugoti
	// kiekvieno krokodilo atskirai, užtenka saugoti tik, kiek ir kokių
	// krokodilų buvo suskaičiuota: krokodilus skirstome į agresyvius ir
	// neagresyvius ir nurodytu sčlygoje tikslumus skaičiuojame jų kiekius.
	int k = 0;
	ifstream input(inputFile);
	input >> k;
	for (int i = 0; i < k; ++i)
	{
		int kiekis;
		int agresyvumas;

		input >> kiekis >> agresyvumas;
		if (1 == agresyvumas)
			++agresyvus[kiekis];
		else
			++neagresyvus[kiekis];
	}
	input.close();

	// sčlygoje pasufleruota, kad dauguma agresyviųjų krokodilų yra labiau žali negu balti;
	int *sumos = new int[skirtingu];

	// ieškome slenksčio
	suma(sumos, agresyvus, skirtingu);
	int klaida = maks;
	int slenkst = slenkstis(sumos, neagresyvus, skirtingu, &klaida);
	
	delete[] sumos;
	delete[] neagresyvus;
	delete[] agresyvus;


	// išvedame hipotezės kuri daro mažiausiai klaidų, rezultatus
	ofstream output(outputFile);
	output << slenkst << " " << klaida << endl;
	output.close();

	/**/
	cout << "slenkstis=" << slenkst << ", klaida=" << klaida << endl;
	/**/

	return 0;
}