Прогноз выдач книг по ближайшим изданиям

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

Используется kNN-регрессия по одному признаку. Для книги с возрастом x_i и нового издания с возрастом q расстояние равно абсолютной разности: d_i = |x_i - q|.

Строки, в которых число выдач обозначено символом -, не участвуют в поиске соседей: целевое значение для них неизвестно. Среди остальных книг выбираются k книг с наименьшими расстояниями, а прогноз равен среднему числу их выдач: y = (y_1 + y_2 + ... + y_k) / k.

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

Формат ввода

В первой строке находятся три целых числа n, k и q:

• n — количество строк каталога;
• k — количество ближайших книг;
• q — возраст нового издания в годах.

В следующих n строках находятся два значения:

• x_i — возраст книги в годах;
• y_i — число выдач этой книги за последний месяц или символ -, если это число неизвестно.

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

Выведите прогнозируемое число выдач с двумя знаками после точки.

Округление выполняется до ближайшей сотой: если следующая цифра равна 5 или больше, сотая увеличивается на 1.

Ограничения

• 1 ≤ n ≤ 2000;
• 1 ≤ k ≤ n;
• 0 ≤ q ≤ 50000;
• 0 ≤ x_i ≤ 50000;
• известное значение y_i является целым числом от 0 до 100000;
• неизвестное значение y_i записывается ровно одним символом -;
• количество строк с известным значением y_i не меньше k.