Выбор числа соседей по фолдам

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

Требуется выбрать гиперпараметр k для метода ближайших соседей по заданным фолдам. При проверке записи из фолда g разрешено использовать только книги из фолдов, номер которых не равен g, и только книги с известным числом выдач.

Для книги с возрастом x соседями считаются k допустимых книг с наименьшим расстоянием |x - x_i|. Если расстояния равны, раньше выбирается книга с меньшим book_id. Прогноз равен среднему числу выдач у выбранных соседей: prediction = (y_1 + y_2 + ... + y_k) / k.

Для каждого кандидата k вычисляется средняя абсолютная ошибка на всех книгах с известным числом выдач: MAE(k) = (1 / m) * Σ |prediction_i - y_i|, где m — количество книг с известным числом выдач. Книги, у которых число выдач равно -1, пропущены: они не участвуют ни в вычислении ошибки, ни в качестве соседей. Требуется вывести значение k с минимальной ошибкой.

В особом случае n = 1 единственная книга имеет известное число выдач, единственный кандидат равен 1, а допустимых соседей нет. Её прогноз считается равным 0.

Формат ввода

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

Во второй строке даны q различных целых чисел k_1, k_2, ..., k_q.

В следующих n строках даны четыре целых числа book_id, age_days, monthly_loans, fold:

• book_id — идентификатор книги;
• age_days — возраст книги в днях;
• monthly_loans — число выдач за месяц, либо -1, если значение пропущено;
• fold — номер фолда книги.

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

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

Округление не требуется: ответом является целое значение k.

Если минимальная MAE достигается у нескольких кандидатов, выведите наименьшее из соответствующих значений k.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ f ≤ n, 1 ≤ q ≤ 8.

1 ≤ book_id ≤ 10^9, все book_id различны.

0 ≤ age_days ≤ 10^9, все значения age_days различны.

monthly_loans = -1 либо 0 ≤ monthly_loans ≤ 10^6.

1 ≤ fold ≤ f; каждый номер фолда от 1 до f встречается хотя бы один раз.

Хотя бы у одной книги число выдач известно.

Если n > 1, для каждой книги с известным числом выдач и для каждого кандидата k существует не менее k допустимых книг из других фолдов с известным числом выдач.

Если n = 1, то f = q = 1, единственный кандидат равен 1, а число выдач единственной книги не пропущено.