Порог разделения посылок по массе

В пункте выдачи хранятся две таблицы. В первой таблице указана масса каждой посылки, во второй — информация о том, была ли посылка выдана с задержкой. Строки таблиц могут идти в разном порядке, поэтому их необходимо сопоставить по идентификатору посылки.

Статус -1 означает, что информация о сроке выдачи пока отсутствует. Такие посылки не участвуют в расчёте. Статус 0 означает выдачу без задержки, статус 1 — выдачу с задержкой.

Необходимо выбрать порог массы t для разделения известных посылок на две группы: в левую группу попадают посылки с массой mass <= t, в правую — посылки с массой mass > t. Порогом может быть только значение массы некоторой известной посылки. Обе получившиеся группы должны быть непустыми.

Для группы S определяется индекс Джини: G(S) = 1 - p_0^2 - p_1^2, где p_0 и p_1 — доли посылок без задержки и с задержкой в группе. Выигрыш от порога равен G(все) - (|левые| / |все|) * G(левые) - (|правые| / |все|) * G(правые).

Требуется вывести порог с наибольшим выигрышем и значение этого выигрыша. Если после исключения неизвестных статусов нельзя получить две непустые группы, требуется вывести NONE 0.000000.

При равенстве наибольшего выигрыша выбирается меньший порог массы.

Формат ввода

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

В следующих n строках дана первая таблица: два целых числа parcel_id и mass — идентификатор посылки и её масса в граммах.

В следующих n строках дана вторая таблица: два целых числа parcel_id и delay_status — идентификатор посылки и статус выдачи.

Каждый идентификатор встречается ровно один раз в первой таблице и ровно один раз во второй таблице.

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

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

Если подходящего порога нет, выведите NONE 0.000000.

Ограничения

1 <= n <= 4000.

1 <= parcel_id <= 10^9.

1 <= mass <= 10^6.

delay_status равен -1, 0 или 1.

Все идентификаторы в каждой из таблиц попарно различны.