Сенсации по последнему рейтингу

В справочнике шахматистов хранятся изменения рейтинга. У одного шахматиста может быть несколько записей: рейтинг менялся после разных туров. Для каждого шахматиста нужно использовать запись с самой поздней датой.

Далее справочник присоединяется к партиям по идентификаторам белых и чёрных. Если у последней записи шахматиста рейтинг указан как NA, его текущий рейтинг неизвестен.

Сенсацией называется партия с решающим результатом, в которой победитель имеет строго меньший текущий рейтинг, чем проигравший. Партии с результатом D и партии, где хотя бы у одного из двух шахматистов текущий рейтинг равен NA, не учитываются. Требуется вывести число сенсаций.

Для партии с известными рейтингами белых R_white и чёрных R_black её вклад равен 1, если результат W и R_white < R_black, либо если результат B и R_black < R_white. Во всех остальных случаях вклад равен 0. Ответ равен сумме вкладов всех партий.

Формат ввода

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

В следующих m строках заданы записи справочника в формате player_id date rating, где player_id — идентификатор шахматиста, date — дата обновления рейтинга в формате ГГГГММДД, rating — целое число или строка NA.

В следующих n строках заданы партии в формате white_id black_id result, где white_id — идентификатор белых, black_id — идентификатор чёрных, а result равен W, B или D. Значение W означает победу белых, B — победу чёрных, D — ничью.

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

Выведите одно целое число — количество сенсаций.

Ограничения

1 ≤ n, 2 ≤ m, n + m ≤ 4000.

Идентификаторы player_id, white_id, black_id состоят из латинских букв, цифр и символа _, имеют длину от 1 до 12.

20200101 ≤ date ≤ 20251231; каждая дата в справочнике является корректной календарной датой. Для одного и того же player_id даты всех его записей различны.

Если rating не равен NA, то это целое число от 100 до 3500.

white_id ≠ black_id. Каждый идентификатор, встречающийся в партиях, имеет хотя бы одну запись в справочнике.

Рейтинги двух шахматистов могут быть равны. При равных рейтингах сенсация не засчитывается. Пустых групп нет: для каждого участника партии существует хотя бы одна строка справочника.