Problem E
Jane Eyre
Anna wants to read the famous book Jane Eyre, but annoyingly its title is somewhat late in the alphabet. This is a problem, since Anna always reads books in alphabetical order; as soon as she finish reading a book, she immediately begins reading the next book in her possession which comes first according to ASCII-order.
To make matters even worse, Anna often receives new books as presents. Such books go into the pile of Anna’s unread books (she will finish the book she is currently reading even if the received book is earlier in the alphabet). If she receives one or more books at the exact same moment as she finishes another book, though, then she will pick her next book among both the books in her existing pile and the newly received books.
Given Anna’s pile of unread books and a schedule for at which points in time Anna’s friends will give her new books, can you figure out when she will finish reading Jane Eyre? Anna reads at a speed of one page per minute.
Input
On the first line are three non-negative integers $n$, $m$, and $k$; here $n$ ($0 \leq n < 100\, 000$) indicates the number of unread books in Anna’s pile (in addition to Jane Eyre), $m$ ($0 \leq m < 100\, 000$) indicates the number of books her friends will give her, and $k$ ($1 \leq k < 100\, 000$) indicates the number of pages in Jane Eyre.
The next $n$ lines describe the other unread books in Anna’s pile; the $i^{\text {th}}$ such line contains a string $s_ i$ ($1 \leq |s_ i| \leq 20$) and a positive integer $k_ i$ ($1 \leq k_ i < 100\, 000$) indicating respectively the title of the book and how many pages it contains. The string $s_ i$ will be enclosed in double quotes ("), and consists of a mixture of spaces and alphanumeric ASCII characters.
Finally follows $m$ lines describing the books Anna’s friends will give her; the $j^{\text {th}}$ such line contains a non-negative integer $t_ j$ ($0 \leq t_ j \leq 1\, 000\, 000\, 000$), a string $s_ j$ ($1 \leq |s_ j| \leq 20$) and a positive integer $k_ j$ ($1 \leq k_ j < 100\, 000$) indicating respectively the time (in minutes from now) Anna will receive the book, the title of the book and how many pages it contains. The string $s_ j$ will be enclosed in double quotes ("), and consists of a mixture of spaces and alphanumeric ASCII characters.
Output
A single integer, the minute at which Anna finish reading Jane Eyre.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 592 "Pride and Predjudice" 432 "Don Quixote" 863 863 "Great Gatsby" 218 1082 "Crime and Punishment" 545 |
1673 |
