Порог дождя по валидации

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

Для порога t станция предсказывает дождь тогда и только тогда, когда балл не меньше t. Среди всех баллов, которые встретились без пропуска в валидационной части, требуется выбрать порог с наибольшей F1-мерой на валидации. Затем этот же порог требуется применить к контрольной части и вычислить F1-меру на ней.

Для набора предсказаний TP — число верно предсказанных дождей, FP — число ложных предсказаний дождя, FN — число пропущенных дождей. F1-мера определяется формулой F1 = 2·TP / (2·TP + FP + FN). Если знаменатель этой формулы равен нулю, F1-мера считается равной нулю. Строки с баллом NA не участвуют ни в подборе порога, ни в вычислении контрольной метрики. Гарантируется, что в каждой части есть хотя бы одна строка с известным баллом.

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

Формат ввода

В первой строке даны два целых числа n и m — число валидационных и контрольных наблюдений.

В следующих n строках записаны данные валидации, затем в следующих m строках записаны данные контроля. Каждая строка содержит балл s и метку y через пробел. Балл s равен целому числу от 0 до 1000 либо строке NA. Метка y равна 0, если дождя не было, и 1, если дождь был.

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

Выведите в одной строке выбранный порог t, затем через пробел F1-меру на контрольной части.

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

Ограничения

1 ≤ n, m ≤ 4000.

0 ≤ s ≤ 1000, если s не равен NA.

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

Длина каждого токена балла не превосходит 4 символов, длина токена метки равна 1.

В валидационной части есть хотя бы один балл, не равный NA. В контрольной части есть хотя бы один балл, не равный NA.