Энтропия статусов заказов

Служба доставки еды анализирует журнал завершённых и незавершённых заказов. Для каждого заказа записан район доставки и итоговый статус.

Статус NA означает, что итог заказа пока неизвестен. Такие строки не используются при расчёте, так как целевая метка в них пропущена. Гарантируется, что после исключения строк со статусом NA остаётся хотя бы один заказ.

Требуется вычислить энтропию Шеннона множества известных статусов заказов. Если для статуса s известно c_s заказов, а всего известных статусов m, то его доля равна p_s = c_s / m, а энтропия равна H = -Σ p_s · log2(p_s), где сумма берётся по всем статусам с положительной частотой. При равенстве частот статусы не объединяются: каждый из них даёт отдельное слагаемое в сумме.

Формат ввода

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

В следующих n строках записаны три значения: order_id, zone, status.

order_id — номер заказа, zone — код района доставки, status — один из статусов OK, LATE, CANCELLED, NA.

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

Выведите одно число — энтропию известных статусов заказов.

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

Ограничения

1 ≤ n ≤ 1000.

1 ≤ order_id ≤ 10^9.

Длина строки zone составляет от 1 до 12 символов латинского алфавита, цифр или символа _.

status имеет длину от 2 до 9 символов и является одним из значений OK, LATE, CANCELLED, NA.

Во входных данных есть хотя бы одна строка, у которой status не равен NA.