Minimum Sum of Maximum House Numbers

You are given n houses numbered from 1 to \(n\) and an integer \(m\) denoting the number of groups. Your task is to split these houses into exactly \(m\) contiguous groups such that the sum of the maximum house numbers in each group is minimized.

For a group, the maximum house number is the last house in that contiguous block. Notice that every group must contain at least one house.

For example, if \(n=10\) and \(m=3\), an optimal grouping is to partition the houses in such a way that the cumulative maximum numbers yield the minimum possible sum, which in this example is 21.

inputFormat

The input consists of two space-separated integers \(n\) and \(m\), where \(n\) is the number of houses and \(m\) is the number of groups.

outputFormat

Output a single integer representing the minimum sum of the maximum house numbers for the optimal grouping.

10 3

21