SPOJ in Gyumri

   Байтландия – замечательная страна, обладающая живописной природой и расположенная в центре континента. Основным источником дохода для населения страны является транзит, так как через страну проходит автомагистраль международного значения М0, вдоль которой расположены все N городов Байтландии.

   До недавних времен в стране не существовало административно-территориального деления, то есть отсутствовали районы, области и округа. Последние несколько десятков лет численность байтландцев значительно выросла, поэтому управлять страной стало сложно. Правительство страны в целях упрощения административного управления приняло решение разделить Байтландию на K районов. Каждый район включает один или более городов. Кроме этого, каждый город должен принадлежать одному из K районов. Правительство Байтландии постановило, что деление на районы должно быть таким, что каждому району отводится определенный отрезок автомагистрали, поэтому все города, расположенные вдоль этого отрезка, принадлежат данному району. То есть, если город B находится между городами А и С и города А и С принадлежат одному району, то и город B принадлежит этому району.

   Известно, что численность населения каждого из N городов Байтландии равна A_i, поэтому для каждого из K районов несложно определить S_j - численность населения соответствующего района, равную суммарной численности населения всех городов, принадлежащих этому району. Правительству Байтландии важно, чтобы численность населения одного района незначительно отличалась от численности населения другого района. Для этого академия наук Байтландии разработала специальный показатель административно-территориального деления S, равный сумме чисел (S_i – S_j)² для всех таких пар (i, j) что 1 ≤ i < j ≤ K.

   Ученым Байтландии удалось доказать, что чем меньше показатель административно-территориального деления S, тем более близки между собой районы по численности населения. Ваша задача – определить среднее количество жителей в районе, которое получится разделением N городов Байтландии на K районов.

Входные данные.

   Первая строка содержит два целых числа, разделенных одним пробелом, это числа N и K (1 ≤ N ≤ 500, 1 ≤ K ≤ 100, K ≤ N) соответственно.

   Вторая строка содержит N целых чисел A_i (1 ≤ A_i ≤ 65536) – численность населения i-го города. Числа разделены одиночными пробелами.

Выходные данные.

   Одно целое число – среднее количество жителей в районе (округленное до целого).

Пример.