Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
43 - ZOJ Monthly, October 2005 - 1006
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.

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

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

17.000
Impossible


Author: LIU, Yaoting


Submit    Status