#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++)
{
for(theb = 0; theb <= b; theb++)
{
int tmp = max(thea * theItem[0] + theb * theItem[1],
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);
}
}
}
}
}
}
}
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;
}