Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
49 - ZOJ Monthly, December 2005 - 1005
Full of Painting II

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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 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

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

Sample Input

8 2 1
1
1 8 0
1 8 0
5 2 2
1 2
3 4 0
3 4 1
300 5 10
2 1 2 6 7 3 1 2 4 2
1 300 0
1 300 1
1 300 2
1 300 2
1 300 4

Sample Output

34
Impossible
34056


Author: LIU, Yaoting


Submit    Status