# Problem F

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 |