import numpy as np
import math as m
import random

# Functions

def getRandomScanD(D, T):
    scanD = np.full(D, -1)
    d = 0
    indx = list(range(len(T)))
    while True:
        if len(T) < 1 or d >= len(scanD):
            return scanD
        n = random.randint(0, len(T)-1)
        scanD[d:d+T[n]] = indx[n]
        d += T[n]
        T = np.delete(T, n)
        indx = np.delete(indx, n)
        i = T < D-d
        T = T[i]
        indx = indx[i]

def getYK(scanD, S, ID):
    Y = np.unique(scanD)
    Y = Y[ Y != -1]
    K = [[0]] * len(Y)
    for n,i in enumerate(Y):
        K[n] = [str(x) for _,x in sorted(zip(S[list(ID[i])], ID[i]),
                                     reverse = True)]
    return Y, K

def rearrangeK(scanD, Y, M, K):
    D = len(scanD)
    nB = max([int(max(i)) for i in K])
    scanB = np.full(nB+1, 0)
    for ni1, Ki in enumerate(K):
        nD = D - (np.argwhere(scanD == Y[ni1])[-1] + 1)
        nK = nD * M[Y[ni1]]
        for ni2, k in enumerate(Ki):
            if ni2 > nK:
                K[ni1] = K[ni1][:nK[0]]
                break
            if (scanB[int(k)] == 1):
                Ki.append(Ki.pop(Ki.index(k)))
            scanB[int(k)] = 1
    return K

def getScore(S, K):
    s = 0
    K = [i for k in K for i in k]
    K = np.array(K)
    K = np.unique(K)
    for k in K:
        s += S[int(k)]
    return s

## Read input
filename = ['a_example.txt', 'b_read_on.txt', 'c_incunabula.txt',
            'd_tough_choices.txt' ,'e_so_many_books.txt',
            'f_libraries_of_the_world.txt']
ans = ['a_ans.txt', 'b_ans.txt', 'c_ans.txt', 'd_ans.txt', 'e_ans.txt',
       'f_ans.txt']
inp = 2

f = open(filename[inp], 'r')
B, L, D = [int(x) for x in f.readline().split()]
S = np.array([int(x) for x in f.readline().split()])
N, T, M = np.full(L, 0), np.full(L, 0), np.full(L, 0)
ID = np.full(L, set())
for i in range(L):
    N[i], T[i], M[i] = [int(x) for x in f.readline().split()]
    ID[i] = set([int(x) for x in f.readline().split()])
f.close()

numIter = 100
count = numIter
maxScore = 0
while (count):
    scanD = getRandomScanD(D, T.copy())
    Y, K = getYK(scanD, S, ID)
    K = rearrangeK(scanD, Y, M, K)
    s = getScore(S, K)
    count -= 1
    print(f'{count} {s}')
    if (s > maxScore):
        print('^^^^^')
        maxScore = s
        maxY = Y.copy()
        maxK = K.copy()
        count = numIter

Y = maxY
K = maxK
f2 = open(ans[inp], 'w')
f2.write(f'{len(Y)}\n')
for n,i in enumerate(Y):
    f2.write(f'{i} {len(K[n])}\n')
    f2.write(f"{' '.join(K[n])}\n")
f2.close()