2173: 宝典2第十一章购物问题

【问题描述】购物问题（shopping.cpp/c/pas）Zju1524

建造太空梯需要的物品非常多，墨老师每周都会交给楚继光一张购物清单，他需要购买清单上所列的物品并且必须全部买齐。最开始，楚继光总是穿梭于商店的过道之间，对每样商品选择最便宜的价格购买，但是他逐渐地厌倦了这种方式，并开始了一种新的尝试──对于商店中的每条过道只走一遍，并严格按照清单上物品的顺序购物。现在你要写一个程序来帮助他购物。你所拥有的信息除了清单所列的物品之外，还包括在他选择的整条路线上依次出现的商品和它的价格，你的任务是计算他购齐所有货物的最小花费。

举个例子，如图所示，楚继光需要购买的货物标号依次是1，1，2，20，他必须从下表中依次选择这四样物品，并使总花费最小（在某些情况下，他也可能根本无法找到一种方案购全所有商品），在这个例子中，他的最小花费是21.30元，即选择0.30元和1元的1号商品，然后选择10元的2号和20号商品。

【输入格式】

       第一行两个数，分别表示清单物品数n (n ≤100)，路线上物品数m(m ≤1000)，   接下来一行n个整数描述购物清单的物品，接下来m行每行一个整数和实数，表示物品的编号和价钱。

【输出格式】

       如果可以买到所有物品，打印最少花费，精确到小数点后两位。

       如果不行，打印“Impossible”

【样例输入1】

4 8

1 1 2 20

2 0.29

1 0.30

20 0.15

1 1.00

5 0.05

2 10.00

20 20.00

20 10.00

【样例输出1】

       21.30

　　【样例输入2】

2 3

1 2

2 0.05

1 10.00

1 3.00

【样例输出2】

Impossible