Problem Statement

The hard disk of a computer has n sectors, where the size stored in the i th sector is denoted by sectorCost[i] , for all 1 ≤ i ≤ n . The hard disk needs to be divided into exactly clusterCount clusters. A cluster division of a hard disk into clusterCount parts looks like this: sectorCost[1...x1], sectorCost[x1 + 1 ... x2], ..., sectorCost[x(clusterCount-1) + 1 ... n] In other words, the sectors are split into clusterCount non-empty contiguous parts. The cost of a part [x, ..., y] is defined as sectorCost[x] + sectorCost[y] , that is, the sum of its first and its last sector cost. The cost of a cluster division is the sum of the costs of all its parts. Find the minimum and the maximum possible costs of a cluster division. Example Given n = 5 , sectorCost = [1, 2, 3, 2, 5] and clusterCount = 3 . Minimum cost: cluster the disk as [1], [2], [3, 2, 5] . Cost = (1 + 1) + (2 + 2) + (3 + 5) = 14 . (1-based indexing) Maximum cost: cluster the disk as [1, 2, 3], [2], [5] . Cost = (1 + 3)