Пары заявок с VIP-клиентом

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

Требуется посчитать число неупорядоченных пар различных заявок, в которых хотя бы одна заявка поступила от клиента класса VIP.

Пусть всего имеется N заявок, а V из них относятся к клиентам класса VIP. Искомое число равно

C(N, 2) - C(N - V, 2),

где C(x, 2) = x(x - 1) / 2 при x >= 2, а C(0, 2) = C(1, 2) = 0.

В таблице клиентов могут встречаться несколько строк с одинаковым client_id. Если это происходит, классом клиента считается значение из первой такой строки во входных данных. Если идентификатор клиента из заявки отсутствует в таблице клиентов, такая заявка считается заявкой от клиента класса BASIC.

При равенстве идентификаторов клиентов в нескольких строках таблицы клиентов используется строка, расположенная раньше во входных данных.

Формат ввода

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

В следующих n строках записаны два целых числа ticket_id и client_id — идентификатор заявки и идентификатор клиента, создавшего заявку.

В следующих m строках записаны client_id и client_class, разделённые пробелом. Значение client_class равно VIP или BASIC.

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

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

Ответ является целым числом, округление не выполняется.

Ограничения

1 <= n <= 1999.

1 <= m <= 1999.

n + m <= 2000.

1 <= ticket_id <= 10^9, все значения ticket_id различны.

1 <= client_id <= 10^9.

Длина строки client_class составляет от 3 до 5 символов.

Значение client_class равно VIP или BASIC.