Разнообразие велосипедов по районам

Городской велопрокат хранит сведения о станциях в одной таблице, а сведения о поездках — в другой. У каждой станции указан район города, а у каждой поездки — станция, с которой она началась, и код велосипеда.

Для каждого района рассматриваются все поездки, начавшиеся на станциях этого района. Числом различных велосипедов района называется количество различных кодов велосипедов среди таких поездок.

Требуется найти максимальное число различных велосипедов среди всех районов. Район, в котором не было ни одной поездки, имеет число различных велосипедов, равное 0. Каждая станция, указанная в таблице поездок, обязательно присутствует в таблице станций.

При равенстве максимума у нескольких районов выводится это общее максимальное число.

Формат ввода

В первой строке даны два целых числа n и m — количество станций и количество поездок.

В следующих n строках записана таблица станций: station_id district, где station_id — идентификатор станции, а district — название района.

В следующих m строках записана таблица поездок: trip_id start_station bike_code, где trip_id — идентификатор поездки, start_station — идентификатор станции начала поездки, bike_code — код велосипеда.

Формат вывода

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

Дробная часть отсутствует, выводится целое число.

Ограничения

1 ≤ n ≤ 1000.

1 ≤ m ≤ 1000.

1 ≤ station_id, trip_id ≤ 10^9.

Все значения station_id в таблице станций различны.

Все значения trip_id в таблице поездок различны.

Каждое значение start_station встречается среди идентификаторов станций из первой таблицы.

Названия районов и коды велосипедов состоят из латинских букв, цифр и символа _, их длина составляет от 1 до 20 символов.