rb是黑暗之魂的忠诚玩家,经历无数次死亡rb终于到达偶像阿尔特留斯的所在地,但rb一进地图就看到地上写着“力有不足者,折返吧”。接着眼前出现m只怪物,每只怪物都有自己的血量hp,rb必须严格按照顺序战胜这些怪物。rb想见偶像的心情胜过了心中的恐惧。已知rb有n套装备,每套装备都有2个属性分别是攻击力atk和耐久度dur。以下是游戏规则:
当装备攻击力atk大于等于怪物血量hp时,rb就能战胜这只怪物,反之,当天的战斗结束。
每战斗一次消耗1点耐久度,耐久度为0就必须结束当天的战斗,所有装备耐久度每天都会回满,rb每天也只能选择一套装备去战斗。
rb想快点见到自己的偶像,但他太笨了,不知道如何选择每天的装备能使他花费的天数最少,所以请求你帮帮他求出所需的最少天数。如果rb无论怎样都无法打败所有怪物,请输出impossible。
多组输入,不超过5组
建议用scanf输入
对于每组数据:
第一行两个整数n,m分别表示rb的装备数量和怪物数量。(1<=n,m<=1000000)
接下来n行,每行两个正整数atk,dur分别表示每套装备的攻击力和耐久度(1<=atk<=1000000)(1<=dur<=int最大范围)
再接下来m个正整数,表示每个怪物的血量hp。(1<=hp<=int最大范围)
对于每组数据输出一行,如果rb无法击败所有的怪物,输出impossible,否则输出所需要的最少天数。
2 4 10 2 9 4 8 7 6 5 2 4 10 2 9 4 8 10 10 9
1 2