Алексей Саватеев и метро

Известный математик Алексей Савватеев утверждает, что побывал на всех станциях метрополитена в России. Вам необходимо написать программу для проверки того, что подобное утверждение может оказаться правдивым.

Будем считать, что в некоторой стране имеется nn городов с метрополитеном. При этом в некоторых городах метрополитен может быть только планируемым, то есть в них пока нет ни одной станции. Суммарно во всех городах имеется mm действующих станций метро. Для каждой станции известна дата ее открытия и город, в котором она находится. Некоторый путешественник совершил kk поездок по городам этой страны. Для каждой поездки известна ее дата и город, который был посещен. Будем считать, что каждая поездка длится ровно один день, и в этот день путешественник успевает внимательно осмотреть только одну станцию метро.

Ваша программа должна определить максимально возможное количество станций метро, которые мог посетить путешественник.

Рассмотрим пример. Есть 2 города, В первом городе 4 станции метро, а во втором — 3 станции. Даты открытия станций в первом городе: 27.08.2005, 30.12.2010, 09.05.2013, 09.05.2013. Путешественник посетил этот город пять раз в следующие даты: 30.12.2000, 30.12.2005, 08.03.2006, 30.12.2010, 30.12.2015. В его первую поездку 30.12.2000 ни одна станция еще не была открыта. В следующую поездку 30.12.2005 он мог посетить первую станцию метро. В третью поездку 08.03.2006 вторая станция еще не была открыта, и путешественник еще не мог ее посетить. В четвертую поездку 30.12.2010 он мог посетить вторую станцию прямо в день ее открытия. Наконец в пятую поездку путешественник мог посетить третью или четвертую станцию, но не обе одновременно. Таким образом, в этом городе путешественник мог побывать на трех станциях.

Даты открытия станций во втором городе: 28.12.2000, 25.06.2005, 07.10.2010. Путешественник посетил этот город два раза: 23.02.2005 и 31.05.2005. В дни поездок вторая и третья станции еще не были открыты, поэтому путешественник мог посетить только одну станцию. Таким образом, ответ равен четырем.

Формат входных данных
В первой строке на вход подается одно натуральное число nn — количество городов. 1\leq n \leq 1001≤n≤100. Города нумеруются числами от 11 до nn. Во второй строке на вход подается еще одно натуральное число mm — количество станций метро в стране. 1\leq m \leq 10001≤m≤1000. Далее в mm строках дается описание станций. Описание каждой станции в одной строке содержит номер города, в котором расположена станция, и дату открытия в формате "дд.мм.гггг". Все станции упорядочены по дате открытия. Далее в одной строке записано число kk — количество поездок путешественника. 1\leq k \leq 10001≤k≤1000. Наконец в последних kk строках дается описание поездок. Описание каждой поездки в одной строке содержит номер города, который посетил путешественник, и дату поездки в формате "дд.мм.гггг" Даты поездок упорядочены по возрастанию и не повторяются. Все даты в файле являются строками ровно из 10 символов. Номер дня и месяца занимают ровно по два символа и при необходимости содержат ведущие нули. Все даты принадлежат диапазону от 13.12.1973 до 13.12.2073.

Формат выходных данных
Вывести одно число — максимальное количество станций метро, которые мог посетить путешественник.

0

Кто прочел условие, скажите - стоит вникать или только время терять?

0