Выбор k по дневнику тренировок

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

Для каждого значения k от 1 до K проводится проверка по фолдам. При проверке тренировки с номером фолда f обучающими считаются все тренировки с известным километражем и номером фолда, не равным f. Среди них выбираются k тренировок с наименьшим расстоянием |x - x_i|, где x — километраж проверяемой тренировки. При равных расстояниях раньше выбирается тренировка с меньшим идентификатором.

Прогнозом считается среднее значение оценок усталости у выбранных k соседей. Для каждого k вычисляется средняя абсолютная ошибка MAE: MAE(k) = (1 / q) · Σ |p_i - y_i|, где сумма берётся по всем q тренировкам с известным километражем, p_i — прогноз, y_i — настоящая оценка усталости.

Требуется вывести значение k с наименьшей MAE. Если минимальная MAE достигается у нескольких значений k, выводится наименьшее из них. Ответ является целым числом, округление не выполняется.

Километраж NA означает пропуск. Такая тренировка не используется ни как проверяемая, ни как обучающая. Гарантируется, что в каждом фолде есть хотя бы одна тренировка с известным километражем и для любого k от 1 до K вне каждого фолда найдётся не менее k тренировок с известным километражем.

Формат ввода

В первой строке заданы три целых числа n K F — число тренировок, наибольшее проверяемое значение k и число фолдов.

В следующих n строках дана первая таблица: идентификатор тренировки id и недельный километраж x. Вместо километража может стоять строка NA.

В следующих n строках дана вторая таблица: идентификатор тренировки id, номер фолда f и целая оценка усталости y.

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

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

Выведите одно целое число — выбранное значение k.

Ограничения

2 ≤ n ≤ 4000.

1 ≤ K ≤ 50.

2 ≤ F ≤ min(n, 10).

1 ≤ id ≤ 10^9.

x равно NA или целому числу от 0 до 300.

1 ≤ f ≤ F.

0 ≤ y ≤ 100.

Длина каждого числового поля не превышает 10 символов, длина строки NA равна 2.