1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <vector>
#include <stdio.h>
#include <algorithm>

//#define READ_FROM_FILE

using namespace std;
#ifdef READ_FROM_FILE
#include <iostream>
#include <fstream>
#include <sstream>
#endif // READ_FROM_FILE


int countBest( const vector< int > & items, vector< int > bags )
{
	int maxB = -1;
	for ( int i=0; i<items.size( ); ++i )
	{
		bool found = false;
		for ( int b=0; b<bags.size( ); ++b )
		{
			if ( items[i] <= bags[b] )
			{
				bags[b] -= items[i];

				if ( maxB < b )
					maxB = b;

				found = true;
				break;
			}
		}
		if ( !found )
		{
			maxB = -1;
			break;
		}
	}
	return maxB;
}

int main( )
{
#ifdef READ_FROM_FILE
	clock_t start = clock();
#endif

//	for ( int tc=1; tc<=20; ++tc )
//	{
//		ostringstream s;
//		s << "pak_tes" << tc << ".in";

	#ifdef READ_FROM_FILE
		//std::ifstream fin ( s.str( ).c_str() );
		std::ifstream fin ( "sample_pak.txt" );

		if ( !fin.is_open( ) )
		{
			std::cout << "No data file" << std::endl;
			return 0;
		}
	#endif // READ_FROM_FILE

		int itemQ;
		int bagQ;

	#ifdef READ_FROM_FILE
		fin >> itemQ >> bagQ;
	#else
		scanf( "%d %d", &itemQ, &bagQ );
	#endif

		vector< int > items( itemQ );
		vector< int > bags( bagQ );

		for ( int i=0; i<itemQ; ++i )
		{
	#ifdef READ_FROM_FILE
			fin >> items[i];
	#else
			scanf( "%d", &items[i] );
	#endif
		}

		for ( int i=0; i<bagQ; ++i )
		{
	#ifdef READ_FROM_FILE
			fin >> bags[i];
	#else
			scanf( "%d", &bags[i] );
	#endif
		}
		sort( bags.rbegin( ), bags.rend( ) );
		sort( items.rbegin( ), items.rend( ) );

		int maxB = countBest( items, bags );


		for ( int i=0; i<itemQ ; ++i )
		{
			for ( int y=0; y<itemQ-1; ++y )
			{
				swap( items[y], items[y+1] );

				int maxB2 = countBest( items, bags );
				if ( maxB2 != -1 && maxB2 < maxB )
					maxB = maxB2;
			}
		}


		if ( maxB == -1 )
		{
			printf( "NIE\n" );
		}
		else
		{
			printf( "%d\n", ++maxB );
		}

//		ostringstream s2;
//		s2 << "pak_tes" << tc << ".out";
//		ifstream f2( s2.str( ).c_str( ) );
//
//		char tab[100];
//		f2 >> tab;
//
//		printf( "%s\n\n", tab );
//
//	}

#ifdef	READ_FROM_FILE
	clock_t end = clock();
	float seconds = (float)(end - start) / CLOCKS_PER_SEC;

	printf( "time - %f\n", seconds);
#endif

	return 0;
}