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

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 I-th number of this line means the price of stuccoing one centiare of wall with I-th 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 I-th square and the color that I-th square should be painted.

For simplify, you can assume that all the sizes of squares are integers.

Output the minimum cost, one line percase, if he can't draw the requirement squares, just output "Impossible".