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

enum { maxdim = 102 };

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

int time[maxdim][maxdim][maxdim]; //time[pos][a][b] = min time to drink a of A, b of B, using items up to (without) pos 
int prev[maxdim][maxdim][maxdim]; //prev[pos][a][b] = three2one(pos of position to get here)

int ans; //min time necessary
int used[maxdim][2]; //used amount of A, B

//including <algorithm> fubar's time
inline int max(int a, int b)
{
	if(a > b) return a;
	else return b;
}

inline int three2one(int pos, int a, int b)
{
	assert(pos >= 0 && pos < maxdim);
	assert(a >= 0 && a < maxdim);
	assert(b >= 0 && b < maxdim);

	return pos * maxdim * maxdim + a * maxdim + b;
}

/** modifies pos, a, b */
inline void one2three(int combined, int &pos, int &a, int &b)
{
	int debugCombined = combined;

	assert(combined >= 0); //lousy

	pos = combined / (maxdim * maxdim);
	combined %= (maxdim * maxdim);

	a = combined / maxdim;
	combined %= maxdim;

	b = combined;

	assert(three2one(pos, a, b) == debugCombined);
}

void go()
{
	int pos, a, b, thea, theb;

	memset(time, 0x3F, sizeof(time)); //inf
	memset(prev, 0xFF, sizeof(prev)); //-1

	time[0][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(a = 0; a <= wanted; a++)
		{
			for(b = 0; b <= wanted; b++)
			{
				for(thea = 0; thea <= a; thea++)
				{
					int cost = thea * theItem[0];
					if(cost > time[pos][a][b])
						break;

					for(theb = 0; theb <= b; theb++)
					{
						assert(cost == thea * theItem[0]);

						cost += theb * theItem[1];

						if(cost > time[pos][a][b])
							break;

						int tmp = max(cost,
						              time[pos - 1][a - thea][b - theb]);

						if(tmp < time[pos][a][b])
						{
							time[pos][a][b] = tmp;
							prev[pos][a][b] = three2one(pos - 1, a - thea, b - theb);
						}

						cost -= theb * theItem[1];
					}
				}

				//printf("pos %d a %d b %d time %d\n", pos, a, b, time[pos][a][b]);
			}
		}
	}
}

void path()
{
	int pos = items, a = wanted, b = wanted;
	int ppos, pa, pb; //prev

	ans = time[pos][a][b];

	printf("ans %d\n", ans);

	while(pos != 0)
	{
		printf("pos %d a %d b %d\n", pos, a, b);

		one2three(prev[pos][a][b], ppos, pa, pb);

		used[pos - 1][0] = a - pa;
		used[pos - 1][1] = b - pb;

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

		pos = ppos;
		a = pa;
		b = pb;
	}
}

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();
	path();

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

	fclose(f);
	return 0;
}