
ZOJ Problem Set  2575
Tingting wants to draw and stucco N squares with N different colors full of the base line of a wall. Give you the number of squares, the length of the wall, the minimum size and the maximal size of each square and the price of stuccoing one centiare of the wall with a special color. Your task is to calculate the minimum cost. Input For each case, the first line is two integers, N, L(1 <= N <= 5, 1 <= L <= 200), N is the number of squares that tingting wants to draw, L is the total length of the wall. The second line is N positive floating numbers, the Ith number of this line means the price of stuccoing one centiare of the wall with Ith color. Then N lines follow, Each line contains two integers, MinI, MaxI(1 <= MinI <= MaxI <= L), which indicates the size of Ith square. For simplify, you can assume that all the sizes of squares are integers. Certainly you should also realize that you can paint each square with the color you like, but each color can only be used once. Output Output the minimum cost, one line percase, if he can't draw the requirement squares, just output "Impossible". Sample Input
2 5 Sample Output
17.000 Author: LIU, Yaoting Source: ZOJ Monthly, October 2005 