1257. Paint House III — K Colours

There are m houses in a row and n colours. houses[i] is 0 if house i is unpainted, otherwise its existing colour. cost[i][j] is the cost to paint house i with colour j+1. A neighbourhood is a maximal group of adjacent houses sharing a colour. Paint all unpainted houses so there are exactly target neighbourhoods, minimizing total cost. Return that minimum cost, or -1 if impossible. The input is JSON {houses, cost, m, n, target}.

Input: JSON {houses, cost, m, n, target}.

Output: Integer — the minimum cost, or -1.

Examples

Input: {"houses":[0,0,0,0,0],"cost":[[1,10],[10,1],[10,1],[1,10],[5,1]],"m":5,"n":2,"target":3}
Output: 9
Explanation: An optimal painting costs 9.

Input: {"houses":[0,2,1,2,0],"cost":[[1,10],[10,1],[10,1],[1,10],[5,1]],"m":5,"n":2,"target":3}
Output: 11
Explanation: Some houses are pre-painted.

Input: {"houses":[3,1,2,3],"cost":[[1,1,1],[1,1,1],[1,1,1],[1,1,1]],"m":4,"n":3,"target":3}
Output: -1
Explanation: All painted with the wrong count.

Constraints

• 1<=m<=100
• 1<=n<=20
• 1<=target<=m

Asked by