
49  ZOJ Monthly, December 2005  1005
Tingting wants to draw and stucco N squares with some colors full of the base line of a wall. The only restriction is that the size of the squares which are in the same color should be different. We know the length of the wall, the quantity of squares, the certain color for painting each square, the cost for each color's painting per square, and also the minimum and the maximum of the size of each square. Your task is to calculate the mininum cost Input For each case, the first line are three integers, L, N, M(1 <= L <= 500, 1 <= N <= 10, 1 <= M <= 10), L is the total length of the wall, N is the number of squares that tingting wants to draw, M is the number of different colors. The second line is M positive integers, the Ith number of this line means the price of stuccoing one centiare of wall with Ith color. Then N lines follow, Each line contains three integers, MinI, MaxI, ColorI(1 <= MinI <= MaxI <= L, 0 <= ColorI < M), which indicates the size of Ith square and the color that Ith square should be painted. For simplify, you can assume that all the sizes of squares are integers. Output Output the minimum cost, one line percase, if he can't draw the requirement squares, just output "Impossible". Sample Input
8 2 1 Sample Output
34 Author: LIU, Yaoting 