Взвешенная энтропия разбиения поездок

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

Значение -1 в поле результата означает, что итог поездки пока неизвестен. Такие поездки не участвуют в вычислении энтропии и её весов. Группа может оказаться пустой после исключения поездок с неизвестным результатом.

Пусть после исключения неизвестных результатов в группе g находится m_g поездок, из них c_{g,0} имеют результат 0, а c_{g,1} имеют результат 1. Энтропия группы равна

H(g) = - sum(p_{g,k} * log2(p_{g,k})),

где сумма берётся по k из множества {0, 1}, p_{g,k} = c_{g,k} / m_g, а слагаемое при c_{g,k} = 0 считается равным нулю. Для пустой группы определяется H(g) = 0.

Пусть M — общее число поездок с известным результатом. Требуется вычислить взвешенную энтропию разбиения: H = (m_0 / M) * H(0) + (m_1 / M) * H(1). Гарантируется, что M >= 1. При равенстве числа поездок с результатами 0 и 1 в некоторой группе оба количества учитываются в формуле на одинаковых условиях.

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

Формат ввода

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

В следующих n строках записаны два целых числа group result:

• group — номер группы разбиения, 0 или 1;
• result — результат поездки: 1 для успешно завершённой поездки, 0 для незавершённой поездки, -1 для неизвестного результата.

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

Выведите одно число — взвешенную энтропию разбиения с тремя знаками после десятичной точки.

Ограничения

1 <= n <= 2000.

group принимает значения от 0 до 1.

result принимает значения от -1 до 1.

Хотя бы для одной поездки значение result равно 0 или 1.