Выбор солнечных панелей для проверки

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

Панель считается подходящей для контрольной проверки, если её фактическая выработка не меньше плана. Запись NA во второй таблице означает пропуск измерения: такая панель не считается подходящей.

Из всех подходящих панелей необходимо выбрать ровно k панелей для проверки. Если подходящих панелей m, то число способов выбора равно числу сочетаний

C(m, k) = m! / (k! · (m - k)!).

При равенстве фактической выработки и плана панель считается подходящей. По ограничениям подходящих панелей не меньше k, поэтому пустой выбор и невозможность выбора не возникают.

Формат ввода

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

В следующих n строках находится первая таблица. Каждая строка содержит идентификатор панели panel_id и целое число plan_kwh — план выработки в киловатт-часах.

В следующих n строках находится вторая таблица. Каждая строка содержит идентификатор панели panel_id и значение actual_kwh — фактическую выработку в киловатт-часах или строку NA.

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

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

Выведите одно целое число — количество способов выбрать ровно k подходящих панелей.

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

Ограничения

1 ≤ n ≤ 1000.

1 ≤ k ≤ n.

1 ≤ plan_kwh ≤ 100000.

actual_kwh равно NA или целому числу от 0 до 100000.

Идентификатор panel_id состоит из строчных латинских букв, цифр и символа _, его длина составляет от 1 до 20 символов.

Во входных данных количество подходящих панелей не меньше k.