from operator import itemgetter

rawFile = open("kittens.txt", "r")
fileCon = [lines.replace("\n", "").split(" ") for lines in rawFile]
rawFile.close()

V = int(fileCon[0][0])
E = int(fileCon[0][1])
R = int(fileCon[0][2])
C = int(fileCon[0][3])
X = int(fileCon[0][4])

Vs = [int(x) for x in fileCon[1]]
Ess = []

start = 2
for i in range(E):
    temp = int(fileCon[start][1])
    temp2 = [-1 for x in range(C)]
    temp3 = (int(fileCon[start][0]))
    for x in range(temp):
        start += 1
        # print(fileCon[start])
        assert (int(fileCon[start][0]) < len(temp2))
        temp2[int(fileCon[start][0])] = int(fileCon[start][1])
    Ess.append((temp3, temp2))
    start += 1

Rs = [[-1 for x in range(E)] for y in range(V)]
ARs = []
counter = 0
tempA = []
for k in range(start, len(fileCon)):
    temp4 = [int(i) for i in fileCon[k]]
    Rs[temp4[0]][temp4[1]] = temp4[2]
    # assert(counter < len(Vs))
    tempA.append([temp4[2], Vs[temp4[0]], temp4[1], temp4[0]])
    counter += 1

tempA.sort()
tempA.reverse()

for x in range(len(tempA)):
    tempA[x].reverse()

tempC = []
key = tempA[0][3]
tempB = []
tempB.append([tempA[0][2], tempA[0][3], tempA[0][1], tempA[0][0]])
for y in range(1, len(tempA) + 1):
    if y == len(tempA):
        key = -1
        y = 0
    if tempA[y][3] == key:
        tempB.append([tempA[y][2], tempA[y][3], tempA[y][1], tempA[y][0]])
        # print (tempB,"here")
    else:
        tempB.sort()
        for x in tempB:
            tempC.append(x)
        # tempC.append(tempB[:])
        # print (tempC)
        tempB = []
        tempB.append([tempA[y][2], tempA[y][3], tempA[y][1], tempA[y][0]])
        key = tempA[y][3]

# print(tempC)
tempD = [[] for x in range(len(tempC))]

# print (len(tempC[0]))
for x in range(len(tempC)):
    tempD[x] = [tempC[x][3], tempC[x][2], tempC[x][0], tempC[x][1]]

ARS = tempD[:]




##########################################################################
solution = []
center_lat=[] # list of all the latency values for the data center



cache_Num = C #number of caches
end_Num = E #number of endpoints
vid_Num = V # number of videos

#list of video size
vid_size = Vs
#size of the chahces
cache_size = X

cache_count=0
while cache_count < cache_Num:
    #solution for the problem
    solution.append([])
    #list just for this cache

    force_list = []


    vid_count=0
    while vid_count<vid_Num:
        end_count = 0

        force_list.append([vid_count, 0])
        while end_count < end_Num:
            #populate the force list table
            force_list[vid_count][1]+=Rs[vid_count][end_count]*(Ess[end_count][0]-Ess[end_count][1][cache_count])
            end_count+=1

        vid_count += 1

    #sort list based off second column

    force_list = sorted(force_list, key=itemgetter(1), reverse=True)

    force_count = 0
    mem_used=0
    while force_count < vid_Num:
        vid_indx = force_list[force_count][0] #should loop through each video index
        used = 0
        if (mem_used + vid_size[vid_indx])<= cache_size:
            used=1
            mem_used += vid_size[vid_indx]
            solution[cache_count].append(vid_indx)



        force_count+=1

    print( str(cache_count) + "/" + str(cache_Num))

    cache_count+=1
fileOut=open("output.txt","w")

print(str(cache_Num),file=fileOut)
for i in range (cache_Num):
    print(i,file=fileOut,end=" ")
    for j in solution[i]:
        print(j,file=fileOut, end= " ")
    print(file=fileOut)

fileOut.close()