Энтропия меток отзывов

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

Строки таблиц сопоставляются по идентификатору отзыва review_id. В расчёт включаются только метки из второй таблицы, для которых такой же идентификатор есть в первой таблице. Записи разметки без соответствующего отзыва и отзывы без метки игнорируются.

Требуется вычислить энтропию Шеннона распределения меток тональности среди сопоставленных записей. Если метка c встретилась count(c) раз, а всего сопоставленных записей k, то её доля равна p(c) = count(c) / k, а энтропия вычисляется по формуле H = -Σ p(c) · log2(p(c)), где сумма берётся по всем меткам с положительной частотой.

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

Формат ввода

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

В следующих n строках даны review_id, app_version, rating — идентификатор отзыва, версия приложения и оценка пользователя.

В следующих m строках даны review_id, label — идентификатор размеченного отзыва и его метка тональности.

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

Выведите значение энтропии Шеннона с тремя знаками после десятичной точки.

Ограничения

1 ≤ n, m ≤ 1000.

Идентификатор review_id состоит из заглавной латинской буквы и от 1 до 5 цифр, его длина от 2 до 6 символов.

Версия app_version состоит из цифр и одной точки, её длина от 3 до 8 символов.

1 ≤ rating ≤ 5.

label — одна из строк POSITIVE, NEGATIVE, NEUTRAL, длина строки от 7 до 8 символов.

Внутри каждой из двух таблиц идентификаторы review_id не повторяются. Входные поля не содержат пропусков.