#include<map>
#include<vector>
#include<bitset>
#include<string>
#include<iostream>
#include<cstdint>
#include<fstream>
#include<unordered_map>
#include<algorithm>
#include<sstream>
#include<memory>
#include<chrono>
#include<set>
#include<iterator>


using namespace std::chrono;


struct Timer
{
    std::string name;
    high_resolution_clock::time_point start_point;

    Timer(const std::string& name) : name(name)
    {
        start_point = high_resolution_clock::now();
    }

    ~Timer()
    {
        high_resolution_clock::time_point finish_point = high_resolution_clock::now();
        std::cout << name << " finished in " << duration_cast<milliseconds>(finish_point - start_point).count() << "ms" << std::endl;
    }
};


struct Book
{
    uint32_t id = 0;
    uint32_t score = 0;

    Book(uint32_t id, uint32_t score) : id(id), score(score)
    {
    }
};


struct Library
{
    uint32_t id = 0;
    uint32_t signup_time = 0;
    uint32_t books_per_day = 0;

    std::vector<uint32_t> books;

    Library(uint32_t id, uint32_t signup_time, uint32_t books_per_day): id(id), signup_time(signup_time), books_per_day(books_per_day)
    {
    }
};


struct Input
{
    uint32_t total_time = 0;
    std::vector<Book> books;
    std::vector<Library> libs;
};


Input read_input(const std::string& path)
{
    Input input;
    std::ifstream input_file(path);
    if (!input_file.is_open())
    {
        std::cout << path << " was not found!" << std::endl;
    }

    int B, L, D;
    input_file >> B >> L >> D;

    input.total_time = D;
    input.libs.reserve(L);
    input.books.reserve(B);

    uint32_t score;
    for (int i = 0; i < B; ++i)
    {
        input_file >> score;
        input.books.push_back(Book(i, score));
    }

    uint32_t N, T, M, bid;
    for (int i = 0; i < L; ++i)
    {
        input_file >> N >> T >> M;
        Library lib(i, T, M);
        lib.books.reserve(N);
        for (int j = 0; j < N; ++j)
        {
            input_file >> bid;
            lib.books.push_back(bid);
        }
        input.libs.push_back(lib);
    }

    return input;
}


struct SolutionItem
{
    uint32_t lib_id;
    std::vector<uint32_t> book_ids;
};


struct Solution
{
    std::vector<SolutionItem> log;
};


void save_solution(const Solution& solution, const std::string& filename)
{
    std::ofstream output_file(filename);
    output_file << solution.log.size() << std::endl;
    for (int i = 0; i < solution.log.size(); ++i)
    {
        const SolutionItem& item = solution.log[i];
        output_file << item.lib_id << " " << item.book_ids.size() << std::endl;
        for (int j = 0; j < item.book_ids.size(); ++j)
        {
            output_file << item.book_ids[j] << " ";
        }
        output_file << std::endl;
    }
}


uint32_t score_solution(const Input& input, const Solution& solution)
{
    uint32_t total_score = 0;
    for (int i = 0; i < solution.log.size(); ++i)
        for (int j = 0; j < solution.log[i].book_ids.size(); ++j)
            total_score += input.books[solution.log[i].book_ids[j]].score;

    return total_score;
}


Solution solve_B(const Input& input)
{
    Solution solution;

    std::vector<uint32_t> book_counter(input.books.size(), 0);
    std::vector<uint32_t> book_scores_normalized(input.books.size(), 0);

    std::vector<Library> libs = input.libs;
    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            ++book_counter[libs[i].books[j]];
        }
    }

    for (int i = 0; i < input.books.size(); ++i)
    {
        book_scores_normalized[i] = (uint32_t)round(input.books[i].score * 1.0 / book_counter[i]);
    }


    std::sort(libs.begin(), libs.end(),
        [](const Library& a, const Library& b) {
            return a.signup_time < b.signup_time || (a.signup_time == b.signup_time && a.books.size() > b.books.size());
        }
    );

    std::vector<bool> used_books(input.books.size(), false);

    uint32_t total_signup = 0;
    for (int i = 0; i < libs.size(); ++i)
    {
        if (i > 0 && i % 100 == 0)
        {
            std::cout << i << "/" << libs.size() << " processed" << std::endl;
        }
        const Library& l = libs[i];
        total_signup += l.signup_time;
        std::vector<std::vector<uint32_t>> books_by_score(100005);
        for (int j = 0; j < l.books.size(); ++j)
        {
            uint32_t book_id = l.books[j];
            if (used_books[book_id])
                continue;

            const Book& b = input.books[l.books[j]];
            books_by_score[b.score].push_back(b.id);
            // books_by_score[book_scores_normalized[i]].push_back(b.id);
        }

        std::vector<uint32_t> sorted_books;
        for (uint32_t s = 1000; s > 0; --s)
        {
            for (int r = 0; r < books_by_score[s].size(); ++r)
            {
                sorted_books.push_back(books_by_score[s][r]);
            }
        }
        if (sorted_books.size() == 0)
        {
            total_signup -= l.signup_time;
            continue;
        }

        SolutionItem item;
        item.lib_id = l.id;
        if (input.total_time < total_signup)
            break;

        uint32_t remaining_books = (input.total_time - total_signup) * l.books_per_day;
        for (int r = 0; r < std::min(remaining_books, sorted_books.size()); ++r)
        {
            uint32_t book_id = sorted_books[r];
            item.book_ids.push_back(book_id);
            used_books[book_id] = true;
        }

        if (item.book_ids.size() > 0)
            solution.log.push_back(item);
    }

    return solution;
}


Solution solve_D(const Input& input)
{
    Solution solution;

    std::vector<uint32_t> book_counter(input.books.size(), 0);
    std::vector<double> book_rarity(input.books.size(), 0);
    std::vector<double> lib_rarity(input.libs.size(), 0);

    std::vector<Library> libs = input.libs;
    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            ++book_counter[libs[i].books[j]];
        }
    }

    for (int j = 0; j < input.books.size(); ++j)
    {
        book_rarity[j] = 1.0 / book_counter[j];
    }

    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            lib_rarity[i] += book_rarity[libs[i].books[j]];
        }
        lib_rarity[i] /= libs[i].books.size();
    }

    std::sort(libs.begin(), libs.end(),
        [&lib_rarity](const Library& a, const Library& b) {
            return lib_rarity[a.id] < lib_rarity[b.id];
        }
    );

    std::vector<bool> used_books(input.books.size(), false);

    uint32_t total_signup = 0;
    for (int i = 0; i < libs.size(); ++i)
    {
        if (i > 0 && i % 100 == 0)
        {
            std::cout << i << "/" << libs.size() << " processed" << std::endl;
        }
        const Library& l = libs[i];
        total_signup += l.signup_time;
        std::vector<std::vector<uint32_t>> books_by_score(100005);
        for (int j = 0; j < l.books.size(); ++j)
        {
            uint32_t book_id = l.books[j];
            if (used_books[book_id])
                continue;

            const Book& b = input.books[l.books[j]];
            books_by_score[b.score].push_back(b.id);
            // books_by_score[book_scores_normalized[i]].push_back(b.id);
        }

        std::vector<uint32_t> sorted_books;
        for (uint32_t s = 1000; s > 0; --s)
        {
            for (int r = 0; r < books_by_score[s].size(); ++r)
            {
                sorted_books.push_back(books_by_score[s][r]);
            }
        }
        if (sorted_books.size() == 0)
        {
            total_signup -= l.signup_time;
            continue;
        }

        SolutionItem item;
        item.lib_id = l.id;
        if (input.total_time < total_signup)
            break;

        uint32_t remaining_books = (input.total_time - total_signup) * l.books_per_day;
        for (int r = 0; r < std::min(remaining_books, sorted_books.size()); ++r)
        {
            uint32_t book_id = sorted_books[r];
            item.book_ids.push_back(book_id);
            used_books[book_id] = true;
        }

        if (item.book_ids.size() > 0)
            solution.log.push_back(item);
    }

    return solution;
}


Solution solve_F(const Input& input)
{
    Solution solution;

    std::vector<uint32_t> book_counter(input.books.size(), 0);
    std::vector<double> book_rarity(input.books.size(), 0);
    std::vector<double> lib_rarity(input.libs.size(), 0);
    std::vector<uint32_t> lib_score(input.libs.size(), 0);
    std::vector<uint32_t> book_scores_normalized(input.books.size(), 0);

    std::vector<Library> libs = input.libs;
    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            ++book_counter[libs[i].books[j]];
            lib_score[i] += input.books[libs[i].books[j]].score;
        }
    }

    for (int j = 0; j < input.books.size(); ++j)
    {
        book_rarity[j] = 1.0 / book_counter[j];
        book_scores_normalized[j] = (uint32_t)round(input.books[j].score * 1.0 / book_counter[j]);
    }

    /*for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            // ++book_counter[libs[i].books[j]];
            lib_score[i] += book_scores_normalized[libs[i].books[j]];
        }
    }*/

    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            lib_rarity[i] += book_rarity[libs[i].books[j]];
        }
        lib_rarity[i] /= libs[i].books.size();
    }

    std::sort(libs.begin(), libs.end(),
        [&lib_score, &lib_rarity](const Library& a, const Library& b) {
            // return lib_score[a.id] / (a.signup_time* a.signup_time) > lib_score[b.id] / (b.signup_time* b.signup_time);
            // return lib_score[a.id] * (uint64_t)a.books_per_day * 1.0 / (a.signup_time * (uint64_t)a.books.size())  > lib_score[b.id] * (uint64_t)b.books_per_day * 1.0 / (b.signup_time * (uint64_t)b.books.size());
            // return lib_score[a.id] * 1.0 / a.signup_time > lib_score[b.id] * 1.0 / b.signup_time;
            // return lib_score[a.id] * 1.0 / a.signup_time / a.signup_time > lib_score[b.id] * 1.0 / b.signup_time / b.signup_time;
            return lib_score[a.id] * lib_rarity[a.id] * 1.0 / a.signup_time > lib_score[b.id] * lib_rarity[b.id] * 1.0 / b.signup_time;
            // return lib_score[a.id] > lib_score[b.id];
        }
    );

    std::vector<bool> used_books(input.books.size(), false);
    std::vector<bool> used_libs(input.libs.size(), false);

    /* std::vector<Library> another_libs = libs;
    std::sort(another_libs.begin(), another_libs.end(),
        [&lib_score](const Library& a, const Library& b) {
            // return lib_score[a.id] / (a.signup_time* a.signup_time) > lib_score[b.id] / (b.signup_time* b.signup_time);
            return a.signup_time < b.signup_time;
            // return lib_score[a.id] > lib_score[b.id];
        }
    ); */

    uint32_t total_signup = 0;
    for (int i = 0; i < libs.size(); ++i)
    {
        if (i > 0 && i % 100 == 0)
        {
            std::cout << i << "/" << libs.size() << " processed" << std::endl;
        }
        const Library& l = libs[i];
        total_signup += l.signup_time;
        std::vector<std::vector<uint32_t>> books_by_score(100005);
        for (int j = 0; j < l.books.size(); ++j)
        {
            uint32_t book_id = l.books[j];
            if (used_books[book_id])
                continue;

            const Book& b = input.books[l.books[j]];
            books_by_score[b.score].push_back(b.id);
            // books_by_score[book_scores_normalized[i]].push_back(b.id);
        }

        std::vector<uint32_t> sorted_books;
        for (uint32_t s = 1000; s > 0; --s)
        {
            for (int r = 0; r < books_by_score[s].size(); ++r)
            {
                sorted_books.push_back(books_by_score[s][r]);
            }
        }
        if (sorted_books.size() == 0)
        {
            total_signup -= l.signup_time;
            continue;
        }

        SolutionItem item;
        item.lib_id = l.id;
        if (input.total_time < total_signup)
            break;

        uint32_t remaining_books = (input.total_time - total_signup) * l.books_per_day;
        for (int r = 0; r < std::min(remaining_books, sorted_books.size()); ++r)
        {
            uint32_t book_id = sorted_books[r];
            item.book_ids.push_back(book_id);
            used_books[book_id] = true;
        }

        if (item.book_ids.size() > 0)
            solution.log.push_back(item);
    }

    return solution;
}


Solution solve_C(const Input& input)
{
    Solution solution;

    std::vector<uint32_t> book_counter(input.books.size(), 0);
    std::vector<double> book_rarity(input.books.size(), 0);
    std::vector<double> lib_rarity(input.libs.size(), 0);
    std::vector<uint32_t> lib_score(input.libs.size(), 0);
    std::vector<uint32_t> book_scores_normalized(input.books.size(), 0);

    std::vector<Library> libs = input.libs;
    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            ++book_counter[libs[i].books[j]];
            //lib_score[i] += input.books[libs[i].books[j]].score;
        }
    }

    for (int j = 0; j < input.books.size(); ++j)
    {
        book_rarity[j] = 1.0 / book_counter[j];
        book_scores_normalized[j] = (uint32_t)round(input.books[j].score * 1.0 / book_counter[j]);
    }

    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            // ++book_counter[libs[i].books[j]];
            // lib_score[i] += book_scores_normalized[libs[i].books[j]];
            lib_score[i] += input.books[libs[i].books[j]].score;
        }
        lib_score[i] = lib_score[i] * libs[i].books_per_day / libs[i].books.size();
    }

    double avg = 0;
    for (int i = 0; i < libs.size(); ++i)
    {
        avg += lib_score[i];
    }
    avg /= libs.size();

    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            lib_rarity[i] += book_rarity[libs[i].books[j]];
        }
        lib_rarity[i] /= libs[i].books.size();
    }

    std::sort(libs.begin(), libs.end(),
        [&lib_score, &lib_rarity, &avg](const Library& a, const Library& b) {
            return lib_score[a.id] / a.signup_time > lib_score[b.id] / b.signup_time;
            // return lib_score[a.id] * (uint64_t)a.books_per_day * 1.0 / (a.signup_time * (uint64_t)a.books.size())  > lib_score[b.id] * (uint64_t)b.books_per_day * 1.0 / (b.signup_time * (uint64_t)b.books.size());
            // return lib_score[a.id] * 1.0 / a.signup_time > lib_score[b.id] * 1.0 / b.signup_time;
            // return lib_score[a.id] * 1.0 / a.signup_time / a.signup_time > lib_score[b.id] * 1.0 / b.signup_time / b.signup_time;
            //return lib_score[a.id] * lib_score[a.id] / b.signup_time > lib_score[b.id] * lib_score[b.id] / b.signup_time;
            // return lib_score[a.id] > lib_score[b.id];
        }
    );

    std::vector<bool> used_books(input.books.size(), false);
    std::vector<bool> used_libs(input.libs.size(), false);

    /* std::vector<Library> another_libs = libs;
    std::sort(another_libs.begin(), another_libs.end(),
        [&lib_score](const Library& a, const Library& b) {
            // return lib_score[a.id] / (a.signup_time* a.signup_time) > lib_score[b.id] / (b.signup_time* b.signup_time);
            return a.signup_time < b.signup_time;
            // return lib_score[a.id] > lib_score[b.id];
        }
    ); */

    uint32_t total_signup = 0;
    for (int i = 0; i < libs.size(); ++i)
    {
        if (i > 0 && i % 100 == 0)
        {
            std::cout << i << "/" << libs.size() << " processed" << std::endl;
        }
        const Library& l = libs[i];
        total_signup += l.signup_time;
        std::vector<std::vector<uint32_t>> books_by_score(100005);
        for (int j = 0; j < l.books.size(); ++j)
        {
            uint32_t book_id = l.books[j];
            if (used_books[book_id])
                continue;

            const Book& b = input.books[l.books[j]];
            books_by_score[b.score].push_back(b.id);
            // books_by_score[book_scores_normalized[i]].push_back(b.id);
        }

        std::vector<uint32_t> sorted_books;
        for (uint32_t s = 1000; s > 0; --s)
        {
            for (int r = 0; r < books_by_score[s].size(); ++r)
            {
                sorted_books.push_back(books_by_score[s][r]);
            }
        }
        if (sorted_books.size() == 0)
        {
            total_signup -= l.signup_time;
            continue;
        }

        SolutionItem item;
        item.lib_id = l.id;
        if (input.total_time < total_signup)
            break;

        uint32_t remaining_books = (input.total_time - total_signup) * l.books_per_day;
        for (int r = 0; r < std::min(remaining_books, sorted_books.size()); ++r)
        {
            uint32_t book_id = sorted_books[r];
            item.book_ids.push_back(book_id);
            used_books[book_id] = true;
        }

        if (item.book_ids.size() > 0)
            solution.log.push_back(item);
    }

    return solution;
}


/*Solution solve_C_BP(const Input& input)
{
    Solution solution;

    std::vector<uint32_t> lib_score(input.libs.size(), 0);
    std::vector<Library> libs = input.libs;
    for (int i = 0; i < libs.size(); ++i)
    {
        for (int j = 0; j < libs[i].books.size(); ++j)
        {
            lib_score[i] += input.books[libs[i].books[j]].score;
        }
    }

    std::vector < std::vector<uint32_t>> dp(2, std::vector<uint32_t>(100005, 0));

    for (int j = 0; j < input.total_time; ++j)
        dp[0][j] = 0;

    for (int i = 1; i < libs.size(); ++i)
        for (int j = 0; j < input.total_time; ++j)
            if (libs[i].signup_time > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - libs[i].signup_time] + lib_score[i])


    return solution;
}*/


int main()
{
    /* {
        Timer timer("Read input");
        Input input_a = read_input("input/a_example.txt");
        Input input_b = read_input("input/b_read_on.txt");
        Input input_c = read_input("input/c_incunabula.txt");
        Input input_d = read_input("input/d_tough_choices.txt");
        Input input_e = read_input("input/e_so_many_books.txt");
        Input input_f = read_input("input/f_libraries_of_the_world.txt");


    } */

    /*
    {
        Timer timer("Solve A");
        Input input_b = read_input("input/a_example.txt");
        Solution solution = solve_B(input_b);
        save_solution(solution, "A.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_b.books.size(); ++i)
            total_book_score += input_b.books[i].score;

        uint32_t score = score_solution(input_b, solution);
        std::cout << "Score A: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/

    /*
    {
        Timer timer("Solve B");
        Input input_b = read_input("input/b_read_on.txt");
        Solution solution = solve_B(input_b);
        save_solution(solution, "B.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_b.books.size(); ++i)
            total_book_score += input_b.books[i].score;

        uint32_t score = score_solution(input_b, solution);
        std::cout << "Score B: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/

    //*
    {
        Timer timer("Solve C");
        Input input_b = read_input("input/c_incunabula.txt");
        Solution solution = solve_C(input_b);
        save_solution(solution, "C.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_b.books.size(); ++i)
            total_book_score += input_b.books[i].score;

        uint32_t score = score_solution(input_b, solution);
        std::cout << "Score C: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/

    /*
    {
        Timer timer("Solve D");
        Input input_d = read_input("input/d_tough_choices.txt");
        Solution solution = solve_D(input_d);
        save_solution(solution, "D.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_d.books.size(); ++i)
            total_book_score += input_d.books[i].score;

        uint32_t score = score_solution(input_d, solution);
        std::cout << "Score D: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/

    /*
    {
        Timer timer("Solve E");
        Input input_b = read_input("input/e_so_many_books.txt");
        Solution solution = solve_F(input_b);
        save_solution(solution, "E.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_b.books.size(); ++i)
            total_book_score += input_b.books[i].score;

        uint32_t score = score_solution(input_b, solution);
        std::cout << "Score E: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/


    /*
    {
        Timer timer("Solve F");
        Input input_b = read_input("input/f_libraries_of_the_world.txt");
        Solution solution = solve_C(input_b);
        save_solution(solution, "F.txt");

        uint32_t total_book_score = 0;
        for (int i = 0; i < input_b.books.size(); ++i)
            total_book_score += input_b.books[i].score;

        uint32_t score = score_solution(input_b, solution);
        std::cout << "Score F: " << score << std::endl;
        std::cout << "Total books score: " << total_book_score << std::endl;
    }
    //*/

    return 0;
}