Anna 想要阅读名著《简·爱》（Jane Eyre），但令人烦恼的是，它的书名在字母表中排得比较靠后。这成了一个问题，因为 Anna 总是按字母顺序阅读书籍；一旦她读完一本书，她会立即开始阅读她手中按 ASCII 码顺序排列的第一本书。

更糟糕的是，Anna 经常会收到作为礼物的新书。这些书会被放入 Anna 的未读书堆中（即使收到的书在字母表中排在前面，她也会先读完当前正在读的书）。不过，如果她在读完一本书的同时收到了新书，她会在现有的书堆和刚收到的书之中选择下一本要读的书。

给定 Anna 的未读书堆以及朋友们送书的时间表，你能算出她会在什么时候读完《简·爱》吗？Anna 的阅读速度是每分钟一页。

Public Domain, British Library via Flickr

输入格式

第一行包含三个非负整数 $n, m$ 和 $k$；其中 $n$ ($0 \le n < 100\,000$) 表示 Anna 书堆中已有的未读书数量（不包括《简·爱》），$m$ ($0 \le m < 100\,000$) 表示朋友们将送给她的书的数量，$k$ ($1 \le k < 100\,000$) 表示《简·爱》的页数。

接下来的 $n$ 行描述了 Anna 书堆中已有的其他未读书；第 $i$ 行包含一个字符串 $s_i$ ($1 \le |s_i| \le 20$) 和一个正整数 $k_i$ ($1 \le k_i < 100\,000$)，分别表示书名和页数。字符串 $s_i$ 将被双引号（"）包围，由空格和字母数字 ASCII 字符组成。

最后 $m$ 行描述了朋友们将送给 Anna 的书；第 $j$ 行包含一个非负整数 $t_j$ ($0 \le t_j \le 1\,000\,000\,000$)，一个字符串 $s_j$ ($1 \le |s_j| \le 20$) 和一个正整数 $k_j$ ($1 \le k_j < 100\,000$)，分别表示 Anna 收到书的时间（从现在开始的分钟数）、书名和页数。字符串 $s_j$ 将被双引号（"）包围，由空格和字母数字 ASCII 字符组成。

输出格式

一个整数，表示 Anna 读完《简·爱》的时刻（分钟）。

样例

样例输入 1

2 2 592
"Pride and Predjudice" 432
"Don Quixote" 863
863 "Great Gatsby" 218
1082 "Crime and Punishment" 545

样例输出 1

1673