#include <stdio.h>

#include <algorithm>
#include <set>
#include <map>
#include <iterator>

typedef signed long Currency;
typedef std::multiset< Currency > CurrencyMultiSet;
typedef std::map< Currency, CurrencyMultiSet > CurrencyMultiSetMap;

struct DataSet {
	Currency monthlyBudget;
	CurrencyMultiSet productPrices;

	DataSet( const char *filename );
};

DataSet::DataSet( const char *filename ) : monthlyBudget( 0 ) {
	FILE *file = fopen( filename, "r" );
	if( !file ) {
		return;
	}

	if( fscanf( file, "%i", &monthlyBudget ) == 1 ) {	
		while( 1 ) {
			unsigned price;
			if( fscanf( file, "%i", &price ) == EOF ) {
				break;
			}
			productPrices.insert( (Currency) price );
		}
	}

	fclose( file );
}

Currency FindOptimalSubMultiSet( const CurrencyMultiSet &elements, const Currency &limit, CurrencyMultiSet &subset ) {
	Currency moneyLeft = limit;
	for( CurrencyMultiSet::const_reverse_iterator iter = elements.rbegin() ; iter != elements.rend() ; iter++ ) {
		const Currency price = *iter;
		if( price <= moneyLeft ) {
			subset.insert( *iter );
			moneyLeft -= price;
		}
		if( moneyLeft < 0 ) {
			break;
		}
	}
	return moneyLeft;
}

CurrencyMultiSet MultiSetWithoutMultiSet( const CurrencyMultiSet &A, const CurrencyMultiSet &B ) {
	CurrencyMultiSet out;	
	std::insert_iterator< CurrencyMultiSet > &insertIterator = std::inserter( out, out.begin() );
	std::set_difference( A.begin(), A.end(), B.begin(), B.end(), insertIterator );
	return out;
}

void OutputMultiSet( const CurrencyMultiSet &elements ) {
	if( !elements.empty() ) {
		for( CurrencyMultiSet::const_iterator iter = elements.begin() ; iter != elements.end() ; iter++ ) {
			const Currency price = *iter;
			printf( "%i ", price );
		}
	} else {
		printf( "nichts " );
	}
}

int main( int argc, char *argv[] ) {
	if( argc < 2 ) {
		return -1;
	}

	DataSet dataSet( argv[ 1 ] );

	unsigned iteration = 1;
	Currency total = 0;
	CurrencyMultiSet solution[2];	
	while( 1 ) {
		CurrencyMultiSet &current = solution[ iteration % 2 ];
		CurrencyMultiSet &old = solution[ (iteration - 1) % 2 ];

		total += dataSet.monthlyBudget;
		current.clear();
		Currency wasted = FindOptimalSubMultiSet( dataSet.productPrices, total, current );
		total -= wasted;
		if( wasted < dataSet.monthlyBudget ) {
			CurrencyMultiSet bought = MultiSetWithoutMultiSet( current, old );
			CurrencyMultiSet sold = MultiSetWithoutMultiSet( old, current );
			printf( "%i. Verkauft: ", iteration );			
			OutputMultiSet( sold );
			printf( "Gekauft: " );
			OutputMultiSet( bought );
			printf( "Gesamtwert: %i Verloren: %i\n", total, wasted );
		} else {
			if( iteration == 1 ) {
				printf( "Es gibt keine Lösung für diesen Datensatz!\n" );
			} // else we're done (see the proof in info.txt)
			break;
		}
		iteration++;
	}

	return 0;
}