Энтропия разбиения фильмов по длительности

Онлайн-кинотеатр готовит данные для модели, предсказывающей оценку фильма. В первой таблице хранится длительность фильмов, а во второй — результаты оценок зрителей для части этих фильмов.

Фильмы нужно разделить по порогу длительности T: в левую группу попадают фильмы длительностью не больше T минут, в правую — остальные фильмы. Требуется вычислить взвешенную энтропию оценок после такого разбиения.

Для непустой группы с долями оценок p0 и p1 энтропия Шеннона определяется формулой H = -p0 · log2(p0) - p1 · log2(p1). Слагаемое 0 · log2(0) считается равным нулю. Энтропия пустой группы равна нулю. Если размеры левой и правой групп равны L и R, а число строк во второй таблице равно m, требуется найти значение (L / m) · Hлев + (R / m) · Hправ.

При равенстве длительности фильма порогу T фильм относится к левой группе.

Формат ввода

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

В следующих n строках дана таблица фильмов. Каждая строка содержит идентификатор фильма movie_id и его длительность duration в минутах.

В следующих m строках дана таблица оценок. Каждая строка содержит идентификатор фильма movie_id и оценку label, равную 0 или 1.

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

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

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

Ограничения

1 ≤ n ≤ 2000.

1 ≤ m ≤ n.

1 ≤ T ≤ 300.

1 ≤ duration ≤ 300.

label равен 0 или 1.

Длина идентификатора movie_id составляет от 1 до 16 символов и состоит из латинских букв, цифр и символа подчёркивания.