Энтропия разбиения заявок поддержки

Служба поддержки провайдера собирает заявки пользователей. Для каждой заявки известны время ожидания первого ответа и итоговый статус: closed, если вопрос был решён, или transferred, если заявку передали специалисту следующей линии.

Для каждого значения порога t заявки разбиваются на две группы: в первую попадают заявки с временем ожидания не более t, во вторую — остальные заявки. Качество такого разбиения измеряется взвешенной энтропией статусов.

Пусть в группе доля заявок со статусом closed равна p, а доля заявок со статусом transferred равна q. Энтропия группы равна H = -p·log2(p) - q·log2(q). Слагаемое вида 0·log2(0) считается равным 0. Взвешенная энтропия разбиения равна (L / n)·H_L + (R / n)·H_R, где L и R — размеры первой и второй групп, а n — общее число заявок. Энтропия пустой группы считается равной 0.

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

Формат ввода

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

В следующих n строках даны два значения: целое число wait_minutes — время ожидания первого ответа в минутах и строка status — итоговый статус заявки.

В следующей строке дано целое число q — количество порогов в запросе.

В последней строке даны q целых чисел t_1, t_2, ..., t_q — пороги времени ожидания в минутах.

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

Выведите наименьшую взвешенную энтропию среди порогов из запроса.

Ответ необходимо вывести ровно с тремя знаками после точки. Значение округляется до ближайшего числа с тремя знаками после точки.

Ограничения

1 ≤ n ≤ 2000.

0 ≤ wait_minutes ≤ 10080.

status имеет длину от 6 до 11 символов и равен closed или transferred.

1 ≤ q ≤ 2000.

0 ≤ t_i ≤ 10080.

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