#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct
{
    int gr;
    int p;
    float r;
} obiect;
int compare(const void *a, const void *b)
{
    const obiect *ob1 = (obiect *)a;
    const obiect *ob2 = (obiect *)b;
    if (ob1->r > ob2->r)
    {
        return -1;
    }
    else
    {
        if (ob1->r < ob2->r)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}
int main()
{
    clock_t start_time = clock();
    clock_t end;
    double time_used = 0;
    int x = 0;
    int n = 0; // nr de obiecte
    int g = 0; // greutatea rucsacului
    printf("Introduceti numarul de obiecte si capacitatea rucsacului");
    scanf("%d%d", &n, &g);
    obiect *ob;
    ob = malloc(sizeof(obiect) * n);
    for (int i = 0; i < n; i++)
    {
        printf("ob[%d].greutate=", i);
        scanf("%d", &ob[i].gr);
        printf("ob[%d].profit=", i);
        scanf("%d", &ob[i].p);
        ob[i].r = ob[i].p / ob[i].gr;
    }
    qsort(ob, n, sizeof(obiect), compare);
    int greutate_cur = 0; // greutatea curenta
    int profit = 0;       // profitul curent
    for (int i = 0; i < n; i++)
    {
        if (ob[i].gr + greutate_cur <= g)
        {
            greutate_cur += ob[i].gr;
            profit += ob[i].p;
        }
    }
    printf("\nprofit_total:%d\n", profit);
    free(ob);
    end = clock();
    time_used = ((double)(end - start_time)) / CLOCKS_PER_SEC;
    printf("%f", time_used);
    return 0;
}