Description

Book scanning
Introduction
Books allow us to discover fantasy worlds and be er understand the world we live in. They enable us to learn about everything from photography to compilers… and of course a good book is a great way to relax!
Google Books is a project that embraces the value books bring to our daily lives. It aspires to bring the world’s books online and make them accessible to everyone. In the last 15 years, Google Books has collected digital copies of 40 million books in more than 400 languages , pa ly by scanning books from libraries and publishers all around the world.
In this competition problem, we will explore the challenges of se ing up a scanning process for millions of books stored in libraries around the world and having them scanned at a scanning facility.
Task
Given a description of libraries and books available, plan which books to scan from which library to maximize the total score of all scanned books, taking into account that each library needs to be signed up before it can ship books.

Problem description
Books
There are B di erent books with IDs from 0 to B –1. Many libraries can have a copy of the same book, but we only need to scan each book once. Each book is described by one parameter: the score that is awarded when the book is scanned.
Libraries
There are L di erent libraries with IDs from 0 to L –1. Each library is described by the following parameters:
● the set of books in the library,
● the time in days that it takes to sign the library up for scanning,
● the number of books that can be scanned each day from the library once the library is signed up.
Time
There are D days from day 0 to day D –1. The rst library signup can sta on day 0. D –1 is the last day during which books can be shipped to the scanning facility.
Library signup
Each library has to go through a signup process before books from that library can be shipped. Only one library at a time can be going through this process (because it involves lots of planning and on-site visits at the library by logistics expe s): the signup process for a library can sta only when no other signup processes are running. The libraries can be signed up in any order .
Books in a library can be scanned as soon as the signup process for that library completes (that is, on the rst day immediately a er the signup process, see the gure below). Books can be scanned in parallel from multiple libraries.

Scanning
All books are scanned in the scanning facility. The entire process of sending the books, scanning them, and returning them to the library happens in one day (note that each library has a maximum number of books that can be scanned from this library per day). The scanning facility is big and can scan any number of books per day.

Input data set
File format
Each input data set is provided in a plain text le. The le contains only ASCII characters with lines ending with a single ‘ ‘ character (also called “UNIX- style” line endings). When multiple numbers are given in one line, they are separated by a single space between each two numbers.

The rst line of the data set contains:
● an integer B ( 1 ≤  B  ≤ 10 5) – the number of di erent books,
● an integer L ( 1  ≤  L  ≤ 10 5) – the number of libraries,
● an integer D ( 1 ≤  D  ≤ 10 5) – the number of days.
This is followed by one line containing B integers: S 0, … , S B-1 , (0 ≤ S i ≤ 103 ) , describing the score of individual books, from book 0 to book B –1.
This is followed by L sections describing individual libraries from library 0 to library L –1. Each such section contains two lines: ● the rst line, which contains:
○ N j ( 1 ≤  N j  ≤ 10 5) – the number of books in library j ,
○ T j (1  ≤  T j  ≤ 10 5) – the number of days it takes to nish the library signup process for library j ,
○ M j (1  ≤  M j  ≤ 10 5) – the number of books that can be shipped from library j to the scanning facility per day, once the library is signed up.
● the second line, which contains N j integers, describing the IDs of the books in the library. Each book ID is listed at most once per library.
The total number of books in all libraries does not exceed 10 6.
Example
Input le Description
6 2 7
1 2 3 6 5 4
5 2 2

0 1 2 3 4
4 3 1

3 2 5 0 There are 6 books, 2 libraries, and 7 days for scanning.
The scores of the books are 1, 2, 3, 6, 5, 4 (in order).
Library 0 has 5 books, the signup process takes 2 days, and the library can ship 2 books per day.
The books in library 0 are: book 0, book 1, book 2, book 3, and book 4.
Library 1 has 4 books, the signup process takes 3 days, and the library can ship 1 book per day.
The books in library 1 are: book 3, book 2, book 5 and book 0.

Note that the example input above contains extra blank lines for clarity, no input le in the Judge System contains blank lines.
Submissions
File format
Your submission describes which books to ship from which library and the order in which libraries are signed up.
The submission le must sta with a line containing the integer A (0 ≤  A ≤ L ) – the number of libraries to sign up (you don’t need to sign up all libraries – the ones you skip are just ignored and no books are scanned from them).
Then, the submission le must describe each library, in the order that you want them to sta the signup process . The description of each library must contain two lines: ● the rst line containing:
○ Y ( 0 ≤  Y  ≤ L – 1) – the ID of the library,
○ K ( 1 ≤ K  ≤  N Y ) – the number of books to be scanned from library Y .
● the second line containing the IDs of the books to scan from that library: k 0, … , k K-1 , (0 ≤ k i ≤ B –1) in the order that they are scanned, without duplicates. Each library must be described only once. Note that:
● You don’t need to scan all books from a library you describe.
● If a library signup process nishes a er D days, its description will be ignored.
● Books shipped a er D days will be ignored.

Note that even though you describe the libraries one a er another in the order by which signup processes are sta ed, the actual scanning of the books happens in parallel for all libraries that are already signed up and still have remaining books to scan.

Example
Submission le Description
2

1 3

5 2 3

0 5

0 1 2 3 4 Two libraries will be signed up for scanning.

The rst library to do the signup process is library 1. A er the signup process it will send 3 books for scanning.

Library 1 will send book 5, book 2, and book 3 in order.
The second library to do the signup process is library 0. A er the signup process it will send 5 books.
Library 0 will send book 0, book 1, book 2, book 3 and book 4 in that order.

Scoring
Your score is the sum of the scores of all books that are scanned within D days. Note that if the same book is shipped from multiple libraries (as books 2 and 3 are in the gure below), the solution will be accepted but the score for the book will be awarded only once.

Figure. Based on the input data set and the submission from the previous sections, books 0, 1, 2, 3, and 5 are scanned by Day 6, and the total score is 16.
The example submission results in this timeline:
● Day 0 to day 2 : signup process for library 1.
● Day 3 : book 5 from library 1 is scanned, signup process for library 0 sta s.
● Day 4 : book 2 from library 1 is scanned, signup process for library 0 nishes.
● Day 5 : book 3 from library 1 is scanned, books 0 and 1 from library 0 are scanned (library 0 can process two books per day).
● Day 6 : books 2 and 3 from library 0 are scanned.
In the end, book 0 , book 1, book 2 , book 3 and book 5 are scanned. Their scores are 1 , 2, 3, 6, and 4, respectively. Which results in a total score of 16 .
Day 6.

Note that there are multiple data sets representing separate instances of the problem. The nal score for your team will be the sum of your best scores for the individual data sets.