제인 에어

Anna는 유명한 책 제인 에어를 읽고 싶어 한다. 그런데 짜증나게도 이 책의 제목은 알파벳 순서에서 꽤 뒤에 온다. Anna는 항상 책을 알파벳 순서로 읽기 때문에 이것은 문제가 된다. 한 책을 다 읽으면, 그녀는 곧바로 가지고 있는 책 중에서 ASCII 순서로 가장 앞서는 책을 읽기 시작한다.

설상가상으로 Anna는 선물로 새 책을 자주 받는다. 그런 책은 Anna의 아직 읽지 않은 책 더미에 들어간다. 그녀는 지금 읽고 있는 책을 다 읽을 때까지는, 받은 책이 알파벳 순서로 더 앞서더라도 그 책을 끝까지 읽는다. 하지만 어떤 책을 다 읽는 바로 그 순간에 한 권 이상의 책을 받으면, 그녀는 기존 더미에 있던 책과 새로 받은 책을 모두 대상으로 다음 책을 고른다.

Anna의 아직 읽지 않은 책 더미와, Anna의 친구들이 언제 새 책을 줄지에 대한 일정이 주어졌을 때, Anna가 제인 에어를 언제 다 읽게 될지 구할 수 있는가? Anna는 분당 한 페이지의 속도로 읽는다.

첫째 줄에 세 개의 음이 아닌 정수 n, m, k가 주어진다. n (0 ≤ n < 100 000)은 Anna의 더미에 있는 (제인 에어를 제외한) 아직 읽지 않은 책의 수, m (0 ≤ m < 100 000)은 친구들이 줄 책의 수, k (1 ≤ k < 100 000)는 제인 에어의 페이지 수다.

다음 n개의 줄은 Anna의 더미에 있는 나머지 아직 읽지 않은 책을 나타낸다. i번째 줄에는 문자열 si (1 ≤ |si| ≤ 20)와 양의 정수 ki (1 ≤ ki < 100 000)가 주어지며, 각각 책의 제목과 페이지 수를 나타낸다. 문자열 si는 큰따옴표(")로 둘러싸여 있고, 공백과 영숫자 ASCII 문자가 섞여 있다.

마지막으로 친구들이 Anna에게 줄 책을 나타내는 m개의 줄이 이어진다. j번째 줄에는 음이 아닌 정수 tj (0 ≤ tj ≤ 1 000 000 000), 문자열 sj (1 ≤ |sj| ≤ 20), 양의 정수 kj (1 ≤ kj < 100 000)가 주어지며, 각각 Anna가 그 책을 받는 시각(지금부터 분 단위), 책의 제목, 페이지 수를 나타낸다. 문자열 sj는 큰따옴표(")로 둘러싸여 있고, 공백과 영숫자 ASCII 문자가 섞여 있다.

Anna가 제인 에어를 다 읽는 분을 나타내는 정수 하나를 출력한다.