def goal(sums):
    return sum([sum(s) ** 2 for s in sums])

class Solver(object):
    def __init__(self, N, M, numbers, poss_min, string):
        self._M = M
        self._N = N
        self._extremum = poss_min
        self._flag = False
        self._partition = None
        self._string = string
        self._numbers = numbers

        self.prepare()

    def prepare(self):
        self._sums = [[] for i in xrange(self._M)]
        thres_sum = [[] for i in xrange(self._M)]
        nm = self._N / self._M
        for j in xrange(self._M):
            for i in xrange(nm):
                thres_sum[j].append(self._numbers[j * nm + i])

        self._minsum = goal(thres_sum)

    def solve(self):
        self.func(self._numbers)

    def func(self, numbers):
#        sys.stdout.write('\r' + self._string.format(self._minsum, *self._sums))

        if goal(self._sums) > self._minsum or self._flag:
            return

        if len(numbers) == 0:
            g = goal(self._sums)
            if g < self._minsum:
                self._minsum = g
                self._partition = np.copy(self._sums)
                if g == self._extremum:
                    self._flag = True
            return

        n = numbers[0]
        for j in xrange(self._M):
            self._sums[j].append(n)
            self.func(numbers[1:])
            self._sums[j] = self._sums[j][:-1]