Точность отбора тренировок

Модель в дневнике бегуна оценивает вероятность того, что запланированная тренировка будет выполнена. Первая таблица содержит прогнозы модели, а вторая — результаты тренировок, которые уже были подтверждены в дневнике.

Для оценки рассматриваются только тренировки, идентификатор которых есть в обеих таблицах. Тренировки без подтверждённого результата не учитываются. Среди учитываемых тренировок необходимо выбрать k с наибольшими вероятностями выполнения.

Требуется вычислить метрику precision@k. Если среди выбранных k тренировок значение метки равно 1 у c тренировок, то

precision@k = c / k.

При равенстве вероятностей тренировки упорядочиваются по возрастанию идентификатора тренировки.

Полученное значение необходимо округлить до трёх знаков после точки по правилу: ближайшее значение, а при точной середине — в большую сторону.

Формат ввода

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

В следующих n строках записана таблица прогнозов. Каждая строка содержит целое число session_id и вероятность probability, разделённые пробелом.

В следующих m строках записана таблица результатов. Каждая строка содержит целое число session_id и целое число completed, разделённые пробелом. Значение completed равно 1, если тренировка выполнена, и 0 иначе.

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

Выведите одно число — значение precision@k, записанное ровно с тремя знаками после точки.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ m ≤ n.

1 ≤ k ≤ m.

1 ≤ session_id ≤ 10^9.

Идентификаторы в таблице прогнозов попарно различны. Идентификаторы в таблице результатов попарно различны и присутствуют в таблице прогнозов.

0 ≤ probability ≤ 1. Вероятность записана десятичным числом не более чем с шестью знаками после точки.

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

В каждой из двух таблиц не более 4000 строк.