Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2575
Full of Painting

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.


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 I-th number of this line means the price of stuccoing one centiare of the wall with I-th color. Then N lines follow, Each line contains two integers, MinI, MaxI(1 <= MinI <= MaxI <= L), which indicates the size of I-th 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 the minimum cost, one line percase, if he can't draw the requirement squares, just output "Impossible".

Sample Input

2 5
1.0 2.0
1 5
1 5
2 5
1.0 2.0
3 4
3 4

Sample Output


Author: LIU, Yaoting
Source: ZOJ Monthly, October 2005
Submit    Status