Информационный выигрыш раздела сайта

В логе школьного сайта для каждого посещения записаны раздел сайта и результат посещения. Значение 1 означает, что посетитель выполнил целевое действие, например отправил заявку на кружок. Значение 0 означает, что целевое действие не выполнено.

Рассматривается одно разбиение для дерева решений. Для каждого различного значения раздела s посещения делятся на две группы: в левой группе находятся строки с разделом s, в правой — все остальные строки. Значение - обозначает неизвестный раздел и считается обычным значением раздела.

Для каждого допустимого разбиения требуется вычислить информационный выигрыш в битах и вывести наибольший из них. Разбиение допустимо, только если обе его группы непусты. Если допустимых разбиений нет, информационный выигрыш считается равным 0.

Энтропия группы с долей единиц p определяется формулой H = -p·log2(p) - (1-p)·log2(1-p), причём слагаемое вида 0·log2(0) считается равным 0. Информационный выигрыш разбиения равен IG = H(Y) - |L|/n · H(L) - |R|/n · H(R), где Y — все посещения, L и R — левая и правая группы.

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

Формат ввода

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

В следующих n строках даны два значения: section и conversion, разделённые пробелом. section — название раздела сайта, conversion — число 0 или 1.

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

Выведите наибольший информационный выигрыш в битах с тремя знаками после точки.

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

Ограничения

1 ≤ n ≤ 2000.

section состоит из строчных латинских букв, символов - и дефисов, длина строки от 1 до 20 символов.

Значение conversion равно 0 или 1.

Количество различных значений section не превышает n.