Порог прогноза решающих шахматных партий

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

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

Для каждого целого порога t от 0 до 100 партия с известной оценкой считается предсказанной как решающая тогда и только тогда, когда её оценка не меньше t. Партии с оценкой - полностью исключаются из расчётов метрики.

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

F1 = 2 · TP / (2 · TP + FP + FN),

где TP — число решающих партий, предсказанных как решающие, FP — число ничьих, предсказанных как решающие, FN — число решающих партий, предсказанных как ничьи. После выбора порога требуется вычислить F1 на контрольной части.

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

Формат ввода

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

Следующие n строк образуют первую таблицу. В каждой строке записаны идентификатор партии id, символ части part и оценка score:

id part score

После этого следуют n строк второй таблицы. В каждой строке записаны идентификатор партии id и фактический результат result:

id result

Значение result равно 1, если партия завершилась решающим результатом, и равно 0, если была ничья.

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

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

Ответ выводится ровно с тремя знаками после десятичной точки.

Ограничения

1 ≤ n ≤ 4000.

Идентификатор id состоит из строчных латинских букв, цифр и символа _, его длина от 1 до 12.

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

part равно V или C.

score равно целому числу от 0 до 100 либо символу -.

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

В валидационной части существует хотя бы одна партия с известной оценкой и результатом 1.