ROC-AUC для наблюдений за птицами

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

Строки таблиц сопоставляются по идентификатору наблюдения. В расчёт входят только идентификаторы, присутствующие в обеих таблицах. Не сопоставленные строки первой и второй таблиц игнорируются.

Требуется вычислить метрику ROC-AUC. Пусть P — число сопоставленных наблюдений с меткой 1, N — число сопоставленных наблюдений с меткой 0. Рассматриваются все P·N пар, состоящие из одного наблюдения с меткой 1 и одного наблюдения с меткой 0. Пусть C — число пар, где оценка наблюдения с меткой 1 строго больше, а T — число пар с равными оценками. Тогда

ROC-AUC = (C + T / 2) / (P · N).

При равенстве оценок пара даёт вклад 1/2 в числитель метрики. Если после сопоставления P = 0 или N = 0, следует вывести 0.000.

Формат ввода

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

В следующих n строках находятся данные первой таблицы: идентификатор наблюдения observation_id и целое число rare_label. Значение rare_label равно 1, если эксперт подтвердил редкую птицу, и 0 в противном случае.

В следующих m строках находятся данные второй таблицы: идентификатор наблюдения observation_id и целое число rarity_score — оценка модели.

Идентификаторы внутри каждой таблицы не повторяются.

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

Выведите одно число — значение ROC-AUC, округлённое до ближайшего значения с тремя знаками после точки. Если значение находится ровно посередине между двумя такими числами, округление выполняется вверх.

Ограничения

1 ≤ n, m ≤ 4000.

2 ≤ n + m ≤ 4000.

Длина каждого идентификатора observation_id составляет от 1 до 12 символов. Идентификатор состоит из строчных латинских букв, цифр и символа подчёркивания.

0 ≤ rare_label ≤ 1.

0 ≤ rarity_score ≤ 1000000.