Minimizing Noise in the Apartment Party

A new apartment with \(m\) buildings has just opened. There are \(n\) students, with exactly one arriving per day. When a student enters a building, a party is held, generating a noise level equal to the current number of students in that building. You are allowed to perform at most \(k\) operations; in each operation you may clear (i.e. kick out) all students from any one building. Note that each day the student arrives first (and causes its noise) and only then can you decide to perform a clearing operation. The goal is to minimize the total noise level summed over all days.

Mathematically, if a building has \(x\) students (over some days) and you perform \(t\) clearing operations on it (thus partitioning the arrivals into \(t+1\) contiguous segments), then the noise contribution from that building is minimized when the students are split as evenly as possible among the \(t+1\) segments. In each segment of length \(L\), the noise is \(\frac{L(L+1)}{2}\). Thus the minimal noise for that building is given by \[ f(x,t)=r\cdot\frac{(a+1)(a+2)}{2}+(t+1-r)\cdot\frac{a(a+1)}{2}, \] where \(a=\lfloor\frac{x}{t+1}\rfloor\) and \(r=x\bmod(t+1)\).

Your task is to distribute the \(n\) students among the \(m\) buildings (you may choose which building each student enters) and decide when to perform the clearing operations (with at most \(k\) operations overall) so that the total noise (the sum of the noises of all buildings) is minimized. Note that you do not have to use all \(k\) operations if they are not needed.

inputFormat

The input consists of a single line containing three integers \(n\), \(m\), \(k\): the number of students, the number of buildings, and the maximum number of clearing operations allowed, respectively.

outputFormat

Output a single integer: the minimum total noise level achievable.

sample

5 2 1

7