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

#define NMAX 100000

struct Video
{
    int ok;
    int size;
};

struct Request
{
    int id;
    int request;
    float ratio;
};

struct Cache
{
    int id;
    int lungime;
    int nrvideo;
    int *video;
};

struct Endpoint {
    int DataCenterLatency;
    int NrCaches;
    struct Cache Caches[NMAX];
    int NrRequests;
//    float Requests[NMAX][3];
    struct Request Requests[NMAX];
};

int main(int argc, char *argv[]) {

    FILE* f;
    FILE *fout = fopen(argv[2], "w");
    f = fopen(argv[1], "r");
    if (f == NULL)
        return 0;

    int R,C,X;
    int V,E;

    fscanf(f,"%d %d %d %d %d ", &V, &E, &R, &C, &X);


    struct Endpoint *endpoint;
    struct Video *videoclip;
    endpoint = (struct Endpoint *) malloc ((E + 1) * sizeof(struct Endpoint));
    videoclip = (struct Video *) malloc ((V + 1) * sizeof(struct Video));


    for(int i = 0; i < V; ++i)
        fscanf(f, "%d ", &videoclip[i].size);



/*    for(int i = 0; i < V; ++i)
        printf("%d ", videoclip[i].size);*/

    for(int i = 0; i < E; i++)
    {
        endpoint[i].DataCenterLatency = 0;
        endpoint[i].NrCaches = 0;
        fscanf(f, "%d ", &endpoint[i].DataCenterLatency);
        fscanf(f, "%d ", &endpoint[i].NrCaches);
        for(int j = 0; j < endpoint[i].NrCaches; ++j)
            fscanf(f,"%d %d ", &endpoint[i].Caches[j].id, &endpoint[i].Caches[j].lungime);
    }

    int idVid , endId;
    float req;

    for(int i = 0; i < E; ++i)
        endpoint[i].NrRequests = 0;

    for(int i = 0; i < R; ++i)
    {

        fscanf(f, "%d %d %f ", &idVid, &endId, &req);
//      printf("%d %d %d\n", idVid, endId, req);
        endpoint[(int)endId].Requests[endpoint[(int)endId].NrRequests].id = idVid;
        endpoint[(int)endId].Requests[endpoint[(int)endId].NrRequests].request = req;
        endpoint[(int)endId].Requests[endpoint[(int)endId].NrRequests].ratio = (float) req / videoclip[(int)idVid].size;
        endpoint[(int)endId].NrRequests++;
    }
//    printf("test");
    /////////AFISARE///////////////

/*

    for(int i = 0; i < E; ++i)
    {
        printf("%d ", endpoint[i].DataCenterLatency);
        printf("%d\n", endpoint[i].NrCaches);

        for(int j = 0; j < endpoint[i].NrCaches; ++j)
            printf("%d %d\n", endpoint[i].Caches[j][0], endpoint[i].Caches[j][1]);
    }

    for(int i = 0; i < E; ++i) {

        printf("%d %d %d\n",endpoint[i].Requests[endpoint[i].NrRequests][0],
                      endpoint[i].Requests[endpoint[i].NrRequests][1],
                          endpoint[i].NrRequests);

    }
*/

 //   sortare
//    printf("\n");
    int aux, i, j, k;
    float auxf;
/*
    for (i = 0; i < E; i++)
        for (j = 0; j < endpoint[i].NrRequests; j++)
*/



    for (i = 0; i < E; i++)
        for (j = 0; j < endpoint[i].NrCaches - 1; j++)
            for (k = j; k < endpoint[i].NrCaches; k++)
                if (endpoint[i].Caches[j].lungime > endpoint[i].Caches[k].lungime)
                {
                    aux = endpoint[i].Caches[j].lungime;
                    endpoint[i].Caches[j].lungime = endpoint[i].Caches[k].lungime;
                    endpoint[i].Caches[k].lungime = aux;

                    aux = endpoint[i].Caches[j].id;
                    endpoint[i].Caches[j].id = endpoint[i].Caches[k].id;
                    endpoint[i].Caches[k].id = aux;
                }


    for (i = 0; i < E; i++)
        for (j = 0; j < endpoint[i].NrRequests - 1; j++)
            for (k = j; k < endpoint[i].NrRequests; k++)
                if (endpoint[i].Requests[j].ratio < endpoint[i].Requests[k].ratio)
                {
                    auxf = endpoint[i].Requests[j].ratio;
                    endpoint[i].Requests[j].ratio = endpoint[i].Requests[k].ratio;
                    endpoint[i].Requests[k].ratio = auxf;

                    aux = endpoint[i].Requests[j].request;
                    endpoint[i].Requests[j].request = endpoint[i].Requests[k].request;
                    endpoint[i].Requests[k].request = aux;

                    aux = endpoint[i].Requests[j].id;
                    endpoint[i].Requests[j].id = endpoint[i].Requests[k].id;
                    endpoint[i].Requests[k].id = aux;
                }

//AFISARE
/*    for (i = 0; i < E; i++)
    {
        printf("-------------- %d -----------\n", i);
        printf("REQUESTS --- RATIO\n");
        for (j = 0; j < endpoint[i].NrRequests; j++)
            {
                printf("%d --- %d --- %f\n", endpoint[i].Requests[j].id, endpoint[i].Requests[j].request, endpoint[i].Requests[j].ratio);
            }
        printf("CACHES\n");
        for (j = 0; j < endpoint[i].NrCaches; j++)
            {
                printf("%d %d\n", endpoint[i].Caches[j].id, endpoint[i].Caches[j].lungime);
            }
    }
*/



    int total;
    for (i = 0; i < E; i++)
    {
        total = 0;
        j = 0;
       //endpoint[i].Requests[j].id sau .ratio
      //videoclip[endpoint[i].Requests[j].id].size
        endpoint[i].Caches[j].video = (int *) malloc (1000000 * sizeof(int));
        total = videoclip[endpoint[i].Requests[j].id].size;
        endpoint[i].Caches[j].nrvideo = 1;
        endpoint[i].Caches[j].video[0] = endpoint[i].Requests[j].id;
        j++;
        while(total < X && j < endpoint[i].NrRequests)
        {
            endpoint[i].Caches[j].video = (int *) malloc (1000000 * sizeof(int));
            if(videoclip[endpoint[i].Requests[j].id].ok==0){
                total += videoclip[endpoint[i].Requests[j].id].size;
                endpoint[i].Caches[j].nrvideo++;
                endpoint[i].Caches[j].video[endpoint[i].Caches[j].nrvideo - 1] = endpoint[i].Requests[j].id;
                videoclip[endpoint[i].Requests[j].id].ok = 1;
            }
            j++;
        }
        if (total > X)
        {
            j--;
            endpoint[i].Caches[j].nrvideo--;
            videoclip[endpoint[i].Requests[j].id].ok = 0;
        }

    }


    int m;
    fprintf(fout, "%d\n", C);
    for (i = 0; i < C; i++)
    {
        fprintf(fout, "%d ", i);
        for (j = 0; j < E; j++)
        {
            for (k = 0; k < endpoint[j].NrCaches; k++)
                if (endpoint[j].Caches[k].id == i)
                    for (m = 0; m < endpoint[j].Caches[k].nrvideo; m++)
                        fprintf(fout, "%d ", endpoint[j].Caches[k].video[m]);
        }
        fprintf(fout, "\n");
    }



    fclose(f);
    fclose(fout);



}