Ошибка прогноза времени обработки заявок

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

Первые k строк используются как обучающая часть. Среди строк обучающей части со временем, отличным от NA, требуется построить прямую y = a·x + b, минимизирующую сумму квадратов ошибок Σ(y_i - (a·x_i + b))².

Остальные строки образуют проверочную часть. Строки, в которых фактическое время равно NA, не участвуют ни в обучении, ни в вычислении ошибки. Требуется найти среднеквадратичную ошибку MSE на известных значениях проверочной части: MSE = (1 / q) · Σ(y_i - (a·x_i + b))², где q — число строк проверочной части с известным временем.

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

Формат ввода

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

В следующих n строках записаны два значения: x и y. Значение x — число сообщений в заявке. Значение y — целое время обработки в минутах либо строка NA, если время неизвестно.

Первые k строк после первой относятся к обучающей части, остальные — к проверочной.

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

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

Ограничения

3 ≤ n ≤ 2000.

2 ≤ k < n.

0 ≤ x ≤ 1000.

Если время обработки известно, то 1 ≤ y ≤ 10000.

Длина обозначения неизвестного времени равна 2 и оно записывается только как NA.