力有不足者,折返吧

TimeLimit:2000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

        rb是黑暗之魂的忠诚玩家,经历无数次死亡rb终于到达偶像阿尔特留斯的所在地,但rb一进地图就看到地上写着“力有不足者,折返吧”。接着眼前出现m只怪物,每只怪物都有自己的血量hp,rb必须严格按照顺序战胜这些怪物。rb想见偶像的心情胜过了心中的恐惧。已知rb有n套装备,每套装备都有2个属性分别是攻击力atk和耐久度dur。以下是游戏规则:

  1. 当装备攻击力atk大于等于怪物血量hp时,rb就能战胜这只怪物,反之,当天的战斗结束。

  2. 每战斗一次消耗1点耐久度,耐久度为0就必须结束当天的战斗所有装备耐久度每天都会回满,rb每天也只能选择一套装备去战斗

    rb想快点见到自己的偶像,但他太笨了,不知道如何选择每天的装备能使他花费的天数最少,所以请求你帮帮他求出所需的最少天数。如果rb无论怎样都无法打败所有怪物,请输出impossible。   

Input

多组输入,不超过5组

建议用scanf输入

对于每组数据:

第一行两个整数n,m分别表示rb的装备数量和怪物数量。(1<=n,m<=1000000)

接下来n行,每行两个正整数atk,dur分别表示每套装备的攻击力和耐久度(1<=atk<=1000000)(1<=dur<=int最大范围)

再接下来m个正整数,表示每个怪物的血量hp。(1<=hp<=int最大范围)


Output

对于每组数据输出一行,如果rb无法击败所有的怪物,输出impossible,否则输出所需要的最少天数。37d3d539b6003af361f91b083a2ac65c1038b613.jpg


SampleInput
2 4
10 2
9 4
8 7 6 5
2 4
10 2
9 4
8 10 10 9
SampleOutput
1
2
Submit
题目统计信息详细
总AC数26
通过人数10
尝试人数12
总提交量69
AC率14.49%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: