Медиана массива целых чисел длины \(n\) это число, стоящее на позиции \(\lceil {\frac{n}{2}} \rceil\) (округление вверх) среди его элементов, упорядоченных по неубыванию. Нумерация позиций начинается с \(1\). Например, медиана массива \([2, 6, 4, 1, 3, 5]\) равна \(3\). Существуют другие определения медианы, но в этой задаче мы будем использовать именно это определение.
Даны два целых числа \(n\) и \(k\) и неубывающий массив целых чисел длины \(nk\). Разделите его элементы на \(k\) массивов размера \(n\), так что каждый элемент попадет в ровно один массив.
Вы хотите, чтобы сумма медиан всех \(k\) массивов была максимально возможной. Найдите эту максимально возможную сумму.
Примечание
Примеры возможных разделений на массивы для всех наборов входных данных первого теста:
Набор входных данных \(1\): \([0, 24], [34, 58], [62, 64], [69, 78]\). Медианы массивов \(0, 34, 62, 69\). Их сумма равна \(165\).
Набор входных данных \(2\): \([27, 61], [81, 91]\). Медианы массивов \(27, 81\). Их сумма равна \(108\).
Набор входных данных \(3\): \([2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]\). Медианы массивов \(91, 36, 18\). Их сумма равна \(145\).
Набор входных данных \(4\): \([3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]\). Медианы массивов \(33, 94, 38, 69\). Их сумма равна \(234\).
Набор входных данных \(5\): \([11, 41]\). Медиана единственного массива \(11\). Сумма единственной медианы равна \(11\).
Набор входных данных \(6\): \([1, 1, 1], [1, 1, 1], [1, 1, 1]\). Медианы массивов \(1, 1, 1\). Их сумма равна \(3\).