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

#define NONE -1

static int debug;

typedef struct _InputItem
{
   int i;               /* item index */
   int v;               /* item value */
   int w;               /* item weight */
} InputItem;

typedef struct _SolverItem {
     int i;             /* index of the selected item */
     int v;             /* cumulated value */
     int w;             /* cumulated weight */
} SolverItem;

typedef struct _Solver
{
   int k;               /* capacity */
   int n;               /* items # */
   InputItem *items;    /* items */
   SolverItem *column;  /* solver column */
} Solver;

static void solve(Solver* solver)
{
   int n, k;
   int v, w;
   int i, j;
   const InputItem *item;
   SolverItem *data;
   const SolverItem *up_left;

   unsigned int counter;

   n = solver->n;
   k = solver->k;

   if (debug > 2)
     {
        printf("\ncurrent V(i,s,W,r)\n");
     }

   /* SOLVE */
   counter = 0;
   item = solver->items;
   for (i = 0; i < n; i++, item++)
     {
        v = item->v;
        w = item->w;
        data = NULL;
        data = solver->column + solver->k;
        up_left = solver->column + (solver->k - w);

        for (j = k; j >= w; j--, data--, up_left--)
          {
             counter++;

             if (data->v < (v + up_left->v))
               {
                  data->i = i;
                  data->v = v + up_left->v;
                  data->w = w + up_left->w;
               }
          }

        if (debug > 2)
          {
             data = solver->column;
             for (j = 0; j <= k; j++, data++)
               printf("  % 4d(% 2d % 2d)\n",
                      data->v, data->i, data->w);
             printf("\n");
          }
     }

   if (debug == 2)
     {
        printf("i=%d:\n", solver->n - 1);
        data = solver->column;
        for (j = 0; j <= k; j++, data++)
          printf("  % 4d(% 2d % 2d)\n",
                 data->v, data->i, data->w);
     }

   if (debug > 0)
     printf("loops count: %u\n", counter);
}

static int check(Solver *solver, int excpected_value)
{
   const SolverItem *data;

   if (excpected_value == NONE)
     return EXIT_SUCCESS;

   data = solver->column + solver->k;
   if (data->v != excpected_value)
     {
        fprintf(stderr,"*** ERROR found %d != %d excpected !",
                data->v, excpected_value);
        return EXIT_FAILURE;
     }

     return EXIT_SUCCESS;
}

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

   int ret;
   int opt;
   int i;
   int excpected_value;
   uint64_t dt;
   struct timespec t0;
   struct timespec t1;

   Solver solver;
   InputItem *item;

   debug = 0;
   excpected_value = NONE;
   while ((opt = getopt(argc, argv, "d:e:")) != -1) {
        switch (opt) {
           case 'd':
              debug = atoi(optarg);
              break;
           case 'e':
              excpected_value = atoi(optarg);
              break;
           default: /* '?' */
              fprintf(stderr, "Usage: %s [-d level] input\n",
                      argv[0]);
              return EXIT_FAILURE;
        }
   }

   if (optind >= argc) {
        fprintf(stderr,"input file missing\n");
        return EXIT_FAILURE;
   }

   if (debug > 0) printf("%s\n", argv[optind]);
   fp = fopen(argv[optind], "r");
   if (fp == NULL)
     {
        fprintf(stderr, "I couldn't open results.dat for reading.\n");
        return 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 > 0) printf("  K:%d N:%d\n", solver.k, solver.n);

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

   solver.column = calloc((solver.k + 1), sizeof(SolverItem));
   if (!solver.column)
     {
        free(solver.items);
        fprintf(stderr, "ERROR: column calloc\n");
        return EXIT_FAILURE;
     }
   for (i = 0; i < (solver.k + 1); i++)
     {
        solver.column[i].i = NONE;
     }

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

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

   clock_gettime(CLOCK_MONOTONIC, &t0);
   solve(&solver);
   clock_gettime(CLOCK_MONOTONIC, &t1);

   ret = check(&solver, excpected_value);

   if (debug > 0)
     {
        dt = ((t1.tv_sec * 1000000000) + t1.tv_nsec) -
           ((t0.tv_sec * 1000000000) + t0.tv_nsec);
        printf(" time %7u [ms]\n", (unsigned int)(dt/1000000));
     }

   free(solver.items);
   free(solver.column);

   return ret;
}