Минимальная MAE прогноза времени доставки

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

Для прогноза используется линейная модель p = a*x + b, где x — индикатор дождя, p — предсказанное время доставки в минутах, а a и b — любые вещественные числа. Для всех заказов требуется найти минимально возможную среднюю абсолютную ошибку MAE.

Если фактическое время заказа равно t_i, то для коэффициентов a и b ошибка определяется формулой MAE(a,b) = (Σ |t_i - (a*x_i+b)|) / n. Требуется вывести минимум этой величины по всем возможным a и b.

При равенстве нескольких подходящих медиан выбирается меньшая из них. Если заказов с некоторым значением индикатора дождя нет, соответствующее предсказание считается равным 0, так как на значение минимальной MAE это не влияет.

Формат ввода

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

В следующих n строках даны два целых числа x_i и t_i: индикатор дождя и фактическое время доставки в минутах.

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

Выведите минимально возможную MAE с шестью знаками после десятичной точки.

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

Ограничения

1 ≤ n ≤ 4000.

x_i равно 0 или 1.

1 ≤ t_i ≤ 300.

Пропусков в данных нет. Повторы строк и одинаковые времена доставки допустимы.