#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int recurrence(int i, int p, int *profit_array, int *size_array) {
    int total_size = 0;

    if (p==0) {
        total_size = 0;
    }
    else if (i==0) {
        total_size = -1;
    }
    else {
        int p_i = profit_array[i-1];
        int s_i = size_array[i-1];

        if (p_i > p) {
            total_size = recurrence((i-1),p, profit_array, size_array);
        }
        else {
            int option1 = recurrence((i-1),p, profit_array, size_array);
            int option2 = option1;
            if (recurrence(i-1,p-p_i,profit_array,size_array) < 0) {
                option2 = -1;
            }
            else {
                option2 = s_i + recurrence((i-1),p-p_i, profit_array, size_array);
            }
            
            if (option1 < 0) {
                total_size = option2;
            }
            else if (option2 < 0) {
                total_size = option1;
            }
            else if (option1 > option2) {
                total_size = option2;
            }
            else {
                total_size = option1;
            }
        }
    }
    return total_size;
}

int main(void) {

    char * line = NULL;
    size_t sz = 0;
    int line_count = 0;
    char profits_buf[100];
    char sizes_buf[100];
    double approx_f = 0.00;
    int capacity = 0;

    while(line_count < 4) {
        ssize_t ln = getline(& line, & sz, stdin);

        if(ln > 0) {
            line_count += 1;
            if (line_count == 1) {
                sscanf(line,"%[^\n]%*c",profits_buf);
            }
            else if (line_count == 2) {
                sscanf(line,"%[^\n]%*c",sizes_buf);
            }
            else if (line_count == 3) {
                capacity = atoi(line);
            }
            else {
                approx_f = atof(line);
            }
        }
    }

    int x = 0;
    int value_count = 1;

    for (x=0;x<strlen(profits_buf);x++) {
        if (isspace(profits_buf[x]) == 0) {
        }
        else {
            value_count += 1;
        }
    }

    int profits[value_count];
    int sizes[value_count];

    char temp[256];
    int digits = 0;
    int y = 0;
    int added_count = 0;

    for (x=0;x<(strlen(profits_buf)+1);x++) {
        if (isspace(profits_buf[x]) == 0 && x<strlen(profits_buf)) {
            temp[digits] = profits_buf[x];
            digits += 1;
        }
        else {
            char new_temp[digits+1];
            for (y=0;y<digits+1;y++) {
                new_temp[y] = temp[y];
            }
            profits[added_count] = atoi(new_temp);
            added_count += 1;
            digits = 0;
            memset(temp, 0, sizeof temp);
        }
    }

    added_count = 0;
    digits = 0;

    for (x=0;x<(strlen(sizes_buf)+1);x++) {
        if (isspace(sizes_buf[x]) == 0 && x<strlen(sizes_buf)) {
            temp[digits] = sizes_buf[x];
            digits += 1;
        }
        else {
            char new_temp[digits+1];
            for (y=0;y<digits+1;y++) {
                new_temp[y] = temp[y];
            }
            sizes[added_count] = atoi(new_temp);
            added_count += 1;
            digits = 0;
            memset(temp, 0, sizeof temp);
        }
    }

    int return_value = 0;
    int i = 0;
    int j = 0;
    int p = 0;
    int sum_profit_prime = 0;
    int profit_len = value_count;
    int max_profit = 0;

    for (i=0; i<profit_len; i++) {
        if (profits[i]>max_profit) {
            max_profit = profits[i];
        }
    }

    printf("\n\n%s\n\n%s ","Given Values:","Profits:");
    for (i=0; i<profit_len; i++) {
        printf(" %d ",profits[i]);
    }
    printf("\n%s ","Sizes:");
    for (i=0; i<profit_len; i++) {
        printf(" %d ",sizes[i]);
    }
    printf("\n%s %d\n","Capacity:",capacity);

    //Factor determined by 1 minus approximation factor
    double epsilon = 1 - approx_f;

    double profit_len_dbl = profit_len + 0;
    double max_profit_dbl = max_profit + 0;

    //K = factor * (max profit / length of profits)
    double k = epsilon * (max_profit_dbl / profit_len_dbl);
    int profits_prime[profit_len];

    printf("\n\n%s%.2f%s%.2f\n","epsilon = 1 - ", approx_f, " = ",epsilon);
    printf("%s%.2f%s%d%s%d%s%f\n","K = ",epsilon, " * ", max_profit, "/", profit_len, " = ", k);
    printf("%s","p' = ");
    for (i=0; i<profit_len; i++) {
        printf("%d%s%.2f ",profits[i],"/",k);
    }
    
    printf("%s"," = ");

    double temp_profit = 0;

    for (i=0; i<profit_len; i++) {
        temp_profit = profits[i] + 0;
        profits_prime[i] = (int)floor(temp_profit/k);
        sum_profit_prime += profits_prime[i];
        printf("%d ", profits_prime[i]);
    }

    int recurrence_array[profit_len+1][sum_profit_prime+1];

    for (i=0; i<(profit_len + 1); i++) {
        for (p=0; p<(sum_profit_prime + 1); p++) {
            recurrence_array[i][p] = recurrence(i,p,profits_prime,sizes);
        }
    }

    printf("%s","\n\n\n");

    //print recurrence relation
    printf("%s","Recurrence Relation: ");
    printf("%s","\n\nA(i, p) =\n{\n");
    printf("%s","if p = 0\t\t0\n");
    printf("%s","else if i = 0\t\tinfinity (shown as '#')\n");
    printf("%s","else if p(i) > p\tA(i-1,p)\n");
    printf("%s","otherwise\t\tmin[A(i-1,p), s(i) + A(i-1,p-p(i))]\n}\n\n\n");

    int solution_size = 0;
    int solution_profit = 0;

    for (i=sum_profit_prime;i>0;i--) {
        for (j=profit_len;j>0;j--) {
            if (recurrence_array[j][i] <= capacity && recurrence_array[j][i] > 0) {
                if (i > solution_profit) {
                    solution_profit = i;
                    solution_size = recurrence_array[j][i];
                }
                else if (i == solution_profit) {
                    if (recurrence_array[j][i]<=solution_size) {
                        solution_profit = i;
                        solution_size = recurrence_array[j][i];
                    }
                }
            }
        }
    }

    //print calculation table
    for (i=0; i<(profit_len + 3); i++) {
        if (i > 1) {
            printf(" %d |",i-2);
        }
        else if (i == 1) {
            printf("-%s-|","-");
        }
        else{
            printf(" %s |"," ");
        }
        for (j=0; j<(sum_profit_prime + 1); j++) {
            if (i==0) {
                printf(" %d ",j);
            }
            else if (i==1) {
                printf("-%s-","-");
            }
            else {
                if (recurrence_array[i-2][j] < 0) {
                    printf(" %s ","#");
                }
                else if (recurrence_array[i-2][j]==solution_size && j==solution_profit) {
                    printf("[%d]",recurrence_array[i-2][j]);
                }
                else {
                    printf(" %d ",recurrence_array[i-2][j]);
                }
            }
        }
        printf("%s","\n");
    }

    printf("\n\n%s%d\n\n","Solution Size = ",solution_size);

    return return_value;
}