#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

static int debug = 0;

typedef uint32_t word_t;
enum { WORD_BITS = sizeof(word_t) * 8 };

static inline int bindex(int b) { return b / WORD_BITS; }
static inline int boffset(int b) { return b % WORD_BITS; }

static inline void set_bit(word_t *bits, int b)
{
   bits[bindex(b)] |= (1 << (boffset(b)));
}

static inline int get_bit(word_t *bits, int b)
{
   return ((bits[bindex(b)] & (1 << (boffset(b)))) >> (boffset(b)));
}

typedef struct _Item
{
   int value;
   int weight;
} Item;

typedef struct _SolverData {
     int v;
     word_t *bits;
} SolverData;

typedef struct _Solver
{
   int k;               // capacity
   int n;               // items #
   int nw;              // # bytes per bits array
   int sum_w;           // sum of item weight
   size_t sd_sz;        // solver data size
   Item *items;         // items
   SolverData *data;    // solver data
} Solver;

static void solve(Solver* solver)
{
   int n, k, nw;
   size_t sd_sz;

   int i, j;
   int v, w;
   int max_c, upper_bound;
   char *data_base;
   Item *item;
   SolverData *c, *p;

   max_c = solver->sum_w;
   sd_sz = solver->sd_sz;
   nw = solver->nw;
   n = solver->n;
   k = solver->k;
   item = solver->items;
   data_base = (char *) solver->data;

   /* SOLVE */
   for (i = 0; i < n; i++, item++)
     {
        v = item->value;
        w = item->weight;
        c = (SolverData *) (data_base + (sd_sz * k));
        p = (SolverData *) (data_base + (sd_sz * (k - w)));

        max_c -= w;
        upper_bound = (((k - max_c) > w) ? (k - max_c) : w );
        for (j = k; j >= upper_bound; j--)
          {
             if (j < w)
               break;
             if ((j >= w) && (c->v < (v + p->v)))
               {
                  c->v = v + p->v;
                  memcpy(c->bits, p->bits, (nw * sizeof(word_t)));
                  set_bit(c->bits, i);
               }
             c = (SolverData *) (((char *) c) - sd_sz);
             p = (SolverData *) (((char *) p) - sd_sz);
          }

        if (debug)
          {
             printf("i=% 4d : ", i);
             for (j = 0; j <= k; j++)
               {
                  c = (SolverData *) (data_base + (sd_sz * j));
                  printf("% 4d ", c->v);
               }
             printf("\n");
          }
     }
}

static void print(Solver* solver)
{
   int b;
   int i;
   int v, w;
   Item *item;
   SolverData *sol;

   v = 0;
   w = 0;
   sol = (SolverData *) (((char *) solver->data) + (solver->sd_sz * solver->k));

   item = solver->items;
   printf("%d %d\n", sol->v, 0);
   for (i = 0; i < solver->n; i++, item++)
     {
        b = get_bit(sol->bits, i);
        printf("%d ", b);
        if (b)
          {
             v += item->value;
             w += item->weight;
          }
     }
   printf("\n");

   if (v != sol->v)
     fprintf(stderr, "ERROR: value %d != %d\n", v, sol->v);
   if (w > solver->k)
     fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
}

int main(int argc, char** argv, char** env)
{
   FILE *fp;
   Solver solver;    // solver

   int i;
   Item *item;
   SolverData *data;

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

   if (debug) 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", &solver.n, &solver.k) != 2)
     {
        fprintf(stderr, "ERROR: read first line\n");
        return EXIT_FAILURE;
     }
   if (debug) printf("  K:%d N:%d\n", solver.k, solver.n);

   /* allocate */
   solver.items = calloc(solver.n, sizeof(Item));
   if (!solver.items)
     {
        fprintf(stderr, "ERROR: items calloc\n");
        return EXIT_FAILURE;
     }

   solver.nw = (solver.n / WORD_BITS + 1);
   solver.sd_sz = sizeof(SolverData) + (solver.nw * sizeof(word_t));
   solver.data= calloc((solver.k + 1), solver.sd_sz);
   if (!solver.data)
     {
        free(solver.items);
        fprintf(stderr, "ERROR: solver calloc\n");
        return EXIT_FAILURE;
     }
   for (i = 0; i <= solver.k; i++)
     {
        data = (SolverData *) (((char *)  solver.data) + solver.sd_sz * i);
        data->bits = (word_t *) (((char *) data) + sizeof(SolverData));
     }

   /* read items */
   solver.sum_w = 0;
   item = solver.items;
   for (i = 0; i < solver.n; i++, item++)
     {
        fscanf(fp, "%d %d\n", &item->value, &item->weight);
        solver.sum_w += item->weight;
     }
   fclose(fp);

   if (debug)
     {
        item = solver.items;
        printf("     index    value   weight\n");
        for (i = 0; i < solver.n; i++, item++)
          printf("  % 8d % 8d % 8d\n", i, item->value, item->weight);
     }

   solve(&solver);
   print(&solver);

   free(solver.items);
   free(solver.data);

   return EXIT_SUCCESS;
}