#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main(int argc, char** argv, char** env)
{
   int k;         // capacity
   int n;         // items #
   int *values;   // items values
   int *weights;  // items weights
   int *solution; // solution
   int *matrix;   // solving matrix

   int i, j;
   int *vp, *wp;
   int v, w, tmp;

   if(argc < 2)
     {
        fprintf(stderr,"input file missing");
        return EXIT_FAILURE;
     }

   FILE *fp;

   /* printf("%s read %s\n", argv[0], argv[1]); */
   fp = fopen(argv[1], "r");
   if (fp == NULL)
     {
        fprintf(stderr, "I couldn't open results.dat for reading.\n");
        exit(EXIT_FAILURE);
     }

   /* read k and n */
   if (fscanf(fp, "%d %d\n", &n, &k) != 2)
     {
        fprintf(stderr, "ERROR: read first line\n");
        return EXIT_FAILURE;
     }
   /* printf("k:%d n:%d\n", k, n); */

   /* allocate */
   values = calloc(n, sizeof(int));
   if (!values)
     {
        fprintf(stderr, "ERROR: values calloc\n");
        return EXIT_FAILURE;
     }
   vp = values;

   weights = calloc(n, sizeof(int));
   if (!weights)
     {
        free(values);
        fprintf(stderr, "ERROR: weights calloc\n");
        return EXIT_FAILURE;
     }
   wp = weights;

   solution = calloc(n, sizeof(int));
   if (!solution)
     {
        free(values);
        free(weights);
        fprintf(stderr, "ERROR: solution calloc\n");
        return EXIT_FAILURE;
     }

   matrix = calloc(k * n, sizeof(int));
   if (!matrix)
     {
        free(values);
        free(weights);
        free(solution);
        fprintf(stderr, "ERROR: matrix calloc\n");
        return EXIT_FAILURE;
     }

   /* read items */
   for (i = 0; i < n; i++)
     fscanf(fp, "%d %d\n", vp++, wp++);
   fclose(fp);

   /* for (i = 0; i < n; i++) */
   /*   printf("%d -> v:%d w:%d\n", i, values[i], weights[i]); */

   /* SOLVE matrix is [i][j] */
#define CURRENT   ((i * k) + j)
#define LEFT      (((i - 1) * k) + j)
#define UPLEFT    (((i - 1) * k) + (j - w))
#define LAST      ((k * n) - 1)
   /* first item */
   i = 0;
   v = values[i];
   w = weights[i];
   for (j = 0; j < k; j++)  // capacities
     {
        if (w <= (j + 1))
          matrix[CURRENT] = v;
     }
   /* following items */
   for (i = 1; i < n; i++)       // items
     {
        v = values[i];
        w = weights[i];
        for (j = 0; j < k; j++)  // capacities
          {
             // item weight to much
             if (w > j + 1)
               {
                  matrix[CURRENT] = matrix[LEFT];
               }
             else
               {
                  /* do not go upper than capacity 0 when moving up left */
                  tmp = v + (((j - w) < 0) ? 0 : matrix[UPLEFT]);
                  if ( tmp > matrix[LEFT])
                    matrix[CURRENT] = tmp;
                  else
                    matrix[CURRENT] = matrix[LEFT];
               }
          }
     }

   /* printf("matrix\n"); */
   /* for (j = 0; j < k; j++) */
   /*   { */
   /*      printf(" %d : ", (j + 1)); */
   /*      for (i = 0; i < n; i++) */
   /*        { */
   /*           printf(" %d", matrix[CURRENT]); */
   /*        } */
   /*      printf("\n"); */
   /*   } */

   j = k - 1;
   for (i = n - 1; i >= 0; i--)
     {
        w = weights[i];
        tmp = matrix[CURRENT];
        if( (tmp != 0) && ((j - w) >= -1) && ( (i == 0) || (tmp != matrix[LEFT])))
          {
             solution[i] = 1;
             j -= w;
          }
        else
             solution[i] = 0;
     }

   v = 0;
   w = 0;
   printf ("%d %d\n", matrix[LAST], 0);
   for (i = 0; i < n; i++)
     {
        printf("%d ", solution[i]);
        if (solution[i]) {
             v += values[i];
             w += weights[i];
        }
     }
   printf("\n");

   if (v != matrix[LAST])
     {
        fprintf(stderr, "ERROR: wrong sum of values %d != %d\n",
                v, matrix[LAST]);
        return EXIT_FAILURE;
     }

   if (w > k)
     {
        fprintf(stderr, "ERROR: wrong sum of weights %d > %d\n", w, k);
        return EXIT_FAILURE;
     }

   free(values);
   free(weights);
   free(solution);
   free(matrix);

   return EXIT_SUCCESS;
}