#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <algorithm>

enum { maxdim = 102 };

int items;
int item[maxdim][2]; //cost A, B
int wanted; //min amount of A, B

/** max_b[pos][a] = max (total) b for given (total) a, within fixed_time, using items upto but without pos */
int max_b[maxdim][maxdim];

/** item_a[pos][a] = the a chosen for item pos when its total is a */
int item_a[maxdim][maxdim];

int fixed_time;
bool succeeded;

int used[maxdim][2];

void dp()
{
	int pos, sum_a, a, b;

	printf("------------------------------------------------\nfixed_time %d\n", fixed_time);

	memset(max_b, 0xFF, sizeof(max_b)); //-1

	max_b[0][0] = 0;

	for(pos = 1; pos <= items; pos++)
	{
		printf("pos %d\n", pos);

		/*
		 * reference to array
		 * http://gcc.gnu.org/ml/gcc/2003-10/msg00714.html
		 */
		int const (&theItem)[2] = item[pos - 1];

		for(sum_a = 0; sum_a <= wanted; sum_a++)
		{
			for(a = 0; a * theItem[0] <= fixed_time && a <= sum_a; a++)
			{
				b = (fixed_time - a * theItem[0]) / theItem[1];

				//impossible
				if(max_b[pos - 1][sum_a - a] == -1)
					continue;

				int tmp = max_b[pos - 1][sum_a - a] + b;

				printf("a %d b %d tmp %d\n", a, b, tmp);

				if(tmp > max_b[pos][sum_a])
				{
					max_b[pos][sum_a] = tmp;
					item_a[pos][sum_a] = a;
				}
			}

			printf("pos %d sum_a %d max_b %d\n", pos, sum_a, max_b[pos][sum_a]);
		}
	}

	if(max_b[items][wanted] >= wanted)
		succeeded = true;
}

void path()
{
	printf("ans fixed_time %d\n", fixed_time);

	int pos, a = wanted;

	for(pos = items; pos > 0; pos--)
	{
		printf("pos %d a %d\n", pos, a);

		used[pos - 1][0] = item_a[pos][a];
		used[pos - 1][1] = max_b[pos][a];

		used[pos][1] -= used[pos - 1][1]; //fix previous

		printf("used: %d %d\n\n", used[pos - 1][0], used[pos - 1][1]);

		a -= used[pos - 1][0];
	}
}

void go()
{
	int bottom = -1, top = maxdim, mid;
	//bottom can't be reached; top can
	
	while(true)
	{
		mid = (bottom + top + 1) / 2;

		fixed_time = mid;
		succeeded = false;
		dp();

		printf("bottom %d top %d mid %d succeeded %d\n", bottom, top, mid, succeeded);

		//done
		if(mid == top)
			break;

		if(succeeded) //maybe less?
			top = mid;
		else //surely more
			bottom = mid;
	}

	path();
}

int main()
{
	int i;
	FILE *f = fopen("lapte.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &items, &wanted);
	for(i = 0; i < items; i++)
		fscanf(f, "%d%d", &item[i][0], &item[i][1]);

	fclose(f);
	f = fopen("lapte.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d\n", fixed_time);
	for(i = 0; i < items; i++)
		fprintf(f, "%d %d\n", used[i][0], used[i][1]);

	fclose(f);
	return 0;
}