Инерция кластеров фильмов

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

Фильм считается полным, если известны и длительность, и оценка. В каждой группе полных фильмов вычисляется центр кластера: средняя длительность \(\bar{x}\) и средняя оценка \(\bar{y}\). Если в некотором кластере нет полных фильмов, его вклад в ответ равен нулю.

Инерцией называется сумма квадратов евклидовых расстояний полных фильмов до центра своего кластера:

\[ I = \sum\limits_{i \text{ — полный фильм}} \left((x_i-\bar{x}_{c_i})^2 + (y_i-\bar{y}_{c_i})^2\right), \]

где \(x_i\) — длительность фильма, \(y_i\) — его оценка, а \(c_i\) — номер его кластера. Фильмы, у которых хотя бы одно из двух значений равно NA, не участвуют ни в вычислении центра, ни в сумме. Если значения фильмов или расстояния совпадают, каждый такой фильм всё равно учитывается отдельным слагаемым.

Формат ввода

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

В следующих n строках записаны четыре значения: film_id, duration, rating, cluster.

film_id — идентификатор фильма без пробелов. Значения duration и rating равны числу или строке NA. cluster — номер кластера фильма.

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

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

Ограничения

• \(1 \le n \le 2000\);
• \(1 \le k \le \min(20, n)\);
• длина film_id от 1 до 30 символов, используются латинские буквы, цифры и символ _;
• duration равно NA или целому числу от 1 до 500;
• rating равно NA или числу от 0 до 10 с не более чем тремя знаками после точки;
• \(1 \le cluster \le k\);
• кластеры без полных фильмов допустимы;
• все числа во входе конечны.