#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ld PI = acos(-1.0);
const ll LINF = (ll)1e18 + 5;
const int INF = (int)1e9 + 5;

template<class T>
T sqr(T x) { return x * x; }

template<class T>
T abs(T x) { return x < 0 ? -x : x; }

template<class T>
ll round(T x) { return x < 0 ? x - 0.5 : x + 0.5; }

template<class T>
bool chmin(T & x, const T & y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T & x, const T & y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}


template<class P, class Q>
ostream & operator <<(ostream & os, const pair<P, Q> & p) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template<class T>
ostream & operator <<(ostream & os, const vector<T> & v) {
    bool was = false;
    os << "{";
    for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
        if (was) {
            os << ", ";
        }
        else {
            was = true;
        }
        os << *it;
    }
    os << "}";
    return os;
}

template<class T>
ostream & operator <<(ostream & os, const set<T> & v) {
    bool was = false;
    os << "{";
    for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
        if (was) {
            os << ", ";
        }
        else {
            was = true;
        }
        os << *it;
    }
    os << "}";
    return os;
}

template<class T>
ostream & operator <<(ostream & os, const multiset<T> & v) {
    bool was = false;
    os << "{";
    for (typename multiset<T>::const_iterator it = v.begin(); it != v.end(); it++) {
        if (was) {
            os << ", ";
        }
        else {
            was = true;
        }
        os << *it;
    }
    os << "}";
    return os;
}

template<class P, class Q>
ostream & operator <<(ostream & os, const map<P, Q> & v) {
    bool was = false;
    os << "{";
    for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
        if (was) {
            os << ", ";
        }
        else {
            was = true;
        }
        os << *it;
    }
    os << "}";
    return os;
}

#define all(x) (x).begin(), (x).end()

string nextToken() {
    static char str[(int)1e6 + 5];
    scanf("%s", str);
    return str;
}

template<class T>
T nextInt() {
    ll x = 0;
    bool p = false;
    char c;
    do {
        c = getchar();
    } while (c <= 32);
    if (c == '-') {
        p = true;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return (p ? -x : x);
}

struct my {
    ll id, cost;
    my() {}
};

struct req {
    ll id, endp, freq;
    req() {}
};

ostream& operator <<(ostream& os, const req& r) {
    return os << "(id=" << r.id << ",endp=" << r.endp << ",freq=" << r.freq << ")";
}

ostream& operator <<(ostream& os, const my& r) {
    return os << "(id=" << r.id << ",cost=" << r.cost <<")";
}

int nVideos, nEndpoints, nRequests, nCaches, capacity;
vector<int> videoSz, videoSzNew;
vector<ll> toDataCenter;
// <ID, cost>
vector<vector<my>> toCacheServer;
vector<ll> minToCacheServer;
vector<req> requests;
int whatPower[2020];
vector<int> blocks[10];
vector<ll> howPopular;
vector<vector<int>> whatRequests;

void calcWhatPower() {
    for (int i = 0; i < 10; i++) {
        whatPower[1 << i] = i;
    }
}

unsigned long long rand64() {
    unsigned long long res = 0;
    for (int i = 0; i < 4; i++) {
        res <<= 16;
        res ^= rand();
    }
    return res;
}

ll rand(ll l, ll r) {
    assert(l <= r);
    return rand64() % (r - l + 1) + l;
}

vector<vector<int>> fillCaches(vector<int> order) {
    vector<vector<int>> res(nCaches);
    vector<int> remain(nCaches, capacity);
    vector<set<int>> was(nCaches);
    auto addVideoToCache = [&](int idx) {
        vector<int> cur = whatRequests[idx];
        sort(all(cur), [](int i, int j) {
           return abs(minToCacheServer[requests[i].endp] - toDataCenter[requests[i].endp]) * 1LL * requests[i].freq >
                   abs(minToCacheServer[requests[j].endp] - toDataCenter[requests[j].endp]) * 1LL * requests[j].freq;
        });
        for (int r : cur) {
            req rq = requests[r];
            int endp = rq.endp;
            bool satisfied = false;
            for (auto p : toCacheServer[endp]) {
                if (was[p.id].count(idx)) {
                    satisfied = true;
                    break;
                } else if (remain[p.id] >= videoSz[idx]) {
                    remain[p.id] -= videoSz[idx];
                    was[p.id].insert(idx);
                    res[p.id].push_back(idx);
                    satisfied = true;
                    break;
                }
            }
            if (satisfied) break;
        }
    };
    for (int idx : order) {
        addVideoToCache(idx);
    }
    return res;
}

ll estimate(vector<vector<int>> caches) {
    vector<set<int>> was(nCaches);
    for (int i = 0; i < nCaches; i++) {
        was[i] = set<int>(all(caches[i]));
    }
    ll res = 0;
    for (req r : requests) {
        bool satisfied = false;
        for (auto p : toCacheServer[r.endp]) {
            if (was[p.id].count(r.id)) {
                res += p.cost * 1LL * r.freq;
                satisfied = true;
                break;
            }
        }
        if (!satisfied) {
            res += toDataCenter[r.endp] * 1LL * r.freq;
        }
    }
    return res;
}

char* dest;

void printCaches(vector<vector<int>> caches) {
    ofstream data(dest);
    data << caches.size() << endl;
    for (int i = 0; i < (int)caches.size(); i++) {
        data << i;
        for (int c : caches[i]) {
            data << " " << c;
        }
        data << endl;
    }
    data.close();
}

int main(int argc, char * argv[]) {
    srand(time(0));

    cerr << argv[1] << endl;

    dest = argv[2];

    freopen(argv[1], "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> nVideos >> nEndpoints >> nRequests >> nCaches >> capacity;
    videoSz.resize(nVideos);

    for (int& x : videoSz) {
        cin >> x;
    }

    cerr << "kittens" << endl;

    toDataCenter.resize(nEndpoints);
    toCacheServer.resize(nEndpoints);

    minToCacheServer.resize(nEndpoints);

    cerr << "!!!" << endl;


    for (int i = 0; i < nEndpoints; i++) {
        cin >> toDataCenter[i];
        int cnt;
        cin >> cnt;
        toCacheServer[i].resize(cnt);
        for (auto& p : toCacheServer[i]) {
            cin >> p.id >> p.cost;
        }
        sort(all(toCacheServer[i]), [](const my& a, const my& b) {
            return a.cost < b.cost;
        });
        ll minimal = LINF;
        for (auto p : toCacheServer[i]) {
            minimal = min(minimal, p.cost);
        }
    }

    cerr << "toDataCenter = " << toDataCenter << endl;
    cerr << "endpoints read" << endl;

    requests.resize(nRequests);

    howPopular.resize(nRequests);

    whatRequests.resize(nVideos);

    int curIdx = 0;
    for (auto& z : requests) {
        cin >> z.id >> z.endp >> z.freq;
        howPopular[z.id] += z.freq;
        whatRequests[z.id].push_back(curIdx);
        curIdx++;
    }

    cerr << "there is was bug?" << endl;

    calcWhatPower();

    cerr << "calc what power" << endl;

    videoSzNew.resize(nVideos);

    for (int i = 0; i < nVideos; i++) {
        videoSzNew[i] = 1;
        while (videoSzNew[i] < videoSz[i]) videoSzNew[i] *= 2;
        //cerr << "videoSzNew[" << i << "] = " << videoSzNew[i] << endl;
        blocks[whatPower[videoSzNew[i]]].push_back(i);
    }

    cerr << "blocks filled" << endl;

    for (int i = 0; i < 10; i++) {
        sort(all(blocks[i]), [](int i, int j) { return howPopular[i] > howPopular[j]; });
    }

    cerr << "blocks created" << endl;

    vector<vector<int>> bestCachesStructure;
    ll bestTime = LINF;
    vector<int> bestTop;

    auto updAns = [&](vector<vector<int>> caches, vector<int> top, ll est) {
        bestCachesStructure = caches;
        bestTop = top;
        bestTime = est;
    };

    auto estimateTop = [&](vector<int> top) {
        vector<int> idxs;
        for (int i = 0; i < 10; i++) {
            for (int z = 0; z < top[i]; z++) {
                idxs.push_back(blocks[i][z]);
            }
        }
        random_shuffle(all(idxs));
        vector<vector<int>> whatCachesContain = fillCaches(idxs);
        ll curTime = estimate(whatCachesContain);
        if (curTime < bestTime) {
            bestCachesStructure = whatCachesContain;
            bestTime = curTime;
            printCaches(bestCachesStructure);
            bestTop = top;
            return curTime;
        }
        return curTime;
    };

    auto getTransProb = [](double de, double t) {
        return exp(-de/t);
    };

    vector<int> top(10);

    for (int i = 0; i < 10; i++) {
        top[i] = rand(0, min<int>(1e9, blocks[i].size()));
    }

    ll curEnergy = estimateTop(top);
    double tempe = 1000;

    for (int iter = 0; iter < 1000; iter++) {
        cerr << "iter = " << iter << ", top = " << top << ", est = " << estimateTop(top) << endl;
        auto newTop = top;
        for (int p = 0; p < 10; p++) {
            if (rand(0, 3) == 0) {
                int howMuch = rand(0, newTop[p]) / 2;
                newTop[p] -= howMuch;
            } else {
                int howMuch = rand(0, (int)blocks[p].size() - newTop[p]) / 2;
                newTop[p] += howMuch;
            }
        }
        cerr << "newTop = " << newTop << endl;
        ll candEnergy = estimateTop(newTop);
        if (candEnergy < curEnergy) {
            curEnergy = candEnergy;
            top = newTop;
        } else {
            double p = getTransProb(candEnergy - curEnergy, tempe);

            if (rand(0, (int)1e6) / 1e6 <= p) {
                curEnergy = candEnergy;
                top = newTop;
            }
        }
        tempe /= abs(log(tempe));
        if (tempe <= 0.00001) {
            break;
        }
    }

}