Problem Statement

Minimum Repaint Cost for Sock Intervals Problem Description Luna has n socks arranged in a row and numbered from 1 to n . Sock i initially has colour colors[i] , where colours are numbered from 1 through k . Over m days Luna wrote down one inclusive interval [left, right] per day. After all repainting is finished, every sock inside such an interval must have the same colour. The requirements of all m days must hold simultaneously . A sock may be repainted at most once . Repainting one sock to colour u costs repaintCost[u] . A sock that already has the colour it is supposed to end up with is not repainted and costs nothing. Socks that are not covered by any interval may be left alone and cost nothing. Print the minimum total cost needed to satisfy every interval requirement. Input Format The first line contains three integers n , k and m — the number of socks, the number of available colours and the number of requirements. The second line contains n integers colors[1] … colors[n]