Chef and Job and Rest

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is working as a programmer. His job schedule is very interesting: he rests for R_{0} minutes, works for some time, then rests for R_{1} minutes, then works some more, and so on.
By the way, Chef has M books he wants to read. Each book has some given number of pages, and Chef reads one page per minute independent of which page of whichever book it is. Chef has two types of books to read: the first type are too interesting for an interrupted read and, therefore, need to be finished in one continuous reading session, that is, some i^{th} resting period or a part of it. Books of the second type are more casual reads which can be split up in any way between different resting periods (read a few pages, then read another book or do the job, and continue later).
Chef is getting tired when switch, that is why each book can be read for some times only once per rest.
Let us take an example: If Chef has a rest period array R = {4,1,1}, and books types to read: (1^{st}, 3 min), (2^{nd}, 3 min). Chef can finish the first book in the first rest period (minutes from 1^{st} to 3^{rd}), and use the 4^{th} minute of first period, along with the second and third periods to finish the second book.
Some books are part of a series, and need to be read in order. In other words, some books can't be started until some other books are done. You are given this information in the form of pairwise dependencies, indicating that one book cannot be started before the other is finished. Chef promises that there are no cycles across these directed dependencies. Each book has a rating, expressed as a positive integer. When Chef finishes a book, his happiness increases by this number.
Scoring
 For each test, your result will be defined as the sum of ratings of books you finish.
 The total score for a submission is the sum of the scores for all test cases.
 Your task is to maximize the total score.
Input
 The first line of each test case contains three integers — N denoting the number of rest periods, M denoting the number of books, and K denoting the number of dependencies. The second line contains N spaceseparated integers R_{1}, R_{2}, …, R_{N} denoting the duration of each period.
 Next M lines describe the books, with the i^{th} line describing the i^{th} book. Each line contains tree integers T_{i}, P_{i} and W_{i}. T_{i} is the type of the i^{th} book. P_{i} is the number of pages in it. W_{i} is the rating of the book.
 Next K lines describe the interbook dependencies. Each line contains two integers — A and B — denoting that book A should be finished before book B can be started. The books are indexed in the order of their description in the input.
Output
 For each rest period, output a single line. The first integer in the line must be K', the number of books you read (fully or partially) in this period. Follow this up with two integers for each book: I — the index of the book you chose (books are enumerated from 1 to M as they are given in input) and W' — the number of minutes you spent on it.
 You are not allowed two print one book twice in one line.
 You can't read the book if it is already finished. Sum of all W' in a line should not be bigger than the rest period duration.
 If you do nothing in a rest period, just print 0.
 Any book of the first type should occur at most once in the output. If Chef reads such a book, it should be done completely in one segment.
 Chef can't start book B until he finishes book A if there is a dependency A, B in the input.
Constraints
 1 ≤ N ≤ 5*10^{4}
 1 ≤ M, K ≤ 10^{5}
 20 ≤ R_{i}≤ 200
 10 ≤ P_{i}≤ 160
 1 ≤ T_{i} ≤ 2
 5 ≤ W_{i} ≤ 1600
 1 ≤ A, B ≤ M
Example
Input: 3 8 2 10 10 10 1 8 2 1 7 1 2 5 4 2 4 1 2 3 1 2 3 4 2 6 1 1 5 1 1 3 3 2 Output: 2 1 8 3 2 2 3 3 2 7 3 4 4 5 3 6 3
Test generation plan
Sum of R_{i}'s will be rand(5 * 10^{5}, 10^{6}). Sum of P_{i}'s will be rand(3 * sum of R's, 8 * sum of R's). Let R_{min} and R_{max} denote the minimum and maximum values of R_{i}, respectively. R_{min} will be rand(20, 100). R_{max} will be rand(R_{min} + 50, 200). We will generate the number of pages of the books in an incremental fashion such that number of pages in a book will be rand(R_{min} / 2, R_{max}* 4 / 5).
There are total 4 types of test files, whose description is given below. Please note that the total number of books of type 2 in each test case will be rand(10, 20), unless stated otherwise.
 Type 1 : We will generate a directed acyclic graph (DAG) encoding the dependencies of books. Each connected component of the DAG has rand(10, 50) vertices. The rating of a book depends on the number of pages in it and the minimum number of books that need to be finished before starting that particular book. The ratio of weight / number of pages will be in the range [1, 10] for books of the first type and [0.5, 1] for that of second type.
 Type 2 : The DAG generator will be same as above. Rating of each book is computed as rand(20,500).
 Type 3 : Same as Type 1, but with no books of the second type.
 Type 4 : Same as Type 1, except that the underlying DAG will be a collections of paths.
Author:  berezin 
Editorial  http://discuss.codechef.com/problems/CHEFJR 
Tags  berezin, challenge, feb16, greedy 
Date Added:  14092014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 