Минимальная MAE линейной модели доставки

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

Рассматривается линейное предсказание времени: p = a·x + b, где x — признак срочной доставки, равный 0 для обычного заказа и 1 для срочного. Коэффициенты a и b можно выбирать любыми действительными числами.

Необходимо найти наименьшую возможную среднюю абсолютную ошибку MAE по всем заказам:

MAE = (|p₁ - y₁| + |p₂ - y₂| + ... + |pₙ - yₙ|) / n,

где yᵢ — фактическое время доставки i-го заказа, а pᵢ = a·xᵢ + b — его предсказание. Требуется вывести только минимальное значение MAE.

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

Формат ввода

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

В следующих n строках даны два целых числа x и y: признак срочной доставки и фактическое время доставки в минутах.

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

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

Ограничения

1 ≤ n ≤ 4000.

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

0 ≤ y ≤ 10000.

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