Взвешенная ошибка прогнозов парковки

Система парковки торгового центра сохраняет фактическое время стоянки по талонам. Отдельная система прогнозирования записывает номер фолда проверки и прогноз времени стоянки для тех же талонов.

Данные поступают двумя таблицами. В первой таблице для каждого талона указано фактическое время стоянки. Во второй таблице указан фолд и прогноз. Значение прогноза -1 означает, что прогноз для талона отсутствует, и такой талон не участвует в расчёте ошибки.

Для каждого фолда с номером j вычисляется средняя абсолютная ошибка MAE: MAE_j = (1 / c_j) * Σ |fact_i - pred_i|, где сумма берётся по талонам с доступным прогнозом в этом фолде, а c_j — число таких талонов. Требуется найти среднее значение MAE по фолдам с весами их размеров: MAE = (Σ (c_j * MAE_j)) / (Σ c_j).

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

Ответ необходимо округлить до четырёх знаков после десятичной точки по правилу: цифра на пятом знаке после точки от 5 до 9 увеличивает четвёртый знак на 1.

Формат ввода

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

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

В следующих n строках записана вторая таблица: три целых числа ticket_id, fold и pred, где ticket_id — номер талона, fold — номер фолда, pred — прогноз времени стоянки в минутах. Значение pred = -1 обозначает отсутствующий прогноз.

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

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

Выведите одно число — взвешенное среднее значение MAE, округлённое до четырёх знаков после десятичной точки.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ k ≤ min(n, 20).

1 ≤ ticket_id ≤ 10^9.

0 ≤ fact ≤ 1440.

1 ≤ fold ≤ k.

pred = -1 или 0 ≤ pred ≤ 1440.

Для каждого номера фолда от 1 до k существует хотя бы одна строка с этим номером фолда и значением pred ≠ -1.