1255. Allocate Mailboxes

Given the positions of houses along a street and an integer k, place exactly k mailboxes so that the sum over all houses of the distance to its nearest mailbox is minimized. Return that minimum total distance. The input is JSON {houses, k}.

Input: JSON {houses, k}.

Output: Integer — the minimum total distance.

Examples

Input: {"houses":[1,4,8,10,20],"k":3}
Output: 5
Explanation: Mailboxes at 3, 9, and 20.

Input: {"houses":[2,3,5,12,18],"k":2}
Output: 9
Explanation: Two optimally placed mailboxes.

Input: {"houses":[7],"k":1}
Output: 0
Explanation: A mailbox at the house.

Constraints

• 1<=n<=100
• 1<=k<=n

Asked by