3585: 勇士的武器升级挑战

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：10 解决：9

题目描述

小勇者要挑战 n 个怪物，每个怪物有一定的血量。 他有一把初始攻击力为 a 的武器，还有 m 个武器升级模块可以安装。 每个升级模块有两个属性： 攻击力加成 uj：安装后，武器攻击力永久增加 uj。 能量消耗 cj：安装这个模块需要消耗 cj 点能量。 小勇者总共只有 E 点能量，不能超过这个限制。 他可以选择其中一些模块安装（也可以一个都不装，或全部装），但： 每个模块最多安装一次。 总消耗能量不能超过 E。 安装完成后，他的最终攻击力为： A = a + 所有选中模块的攻击力加成之和 然后他用这把武器去打 n 个怪物。打每个怪物需要的回合数是： ⌈ 怪物血量 hi / 最终攻击力 A ⌉ 向上取整：比如 ⌈5/3⌉ = 2，因为 3 点攻击力打 5 血要打 2 回合。 总战斗回合数 = 所有怪物所需回合之和。

输入

第 1 行：四个整数 n, m, a, E

  • n：怪物数量
  • m：升级模块数量
  • a：初始攻击力
  • E：总能量上限

第 2 行：n 个整数 h1, h2, …, hn，表示每个怪物的血量

接下来 m 行：每行两个整数 uj, cj，表示第 j 个模块的攻击力加成和能量消耗

输出

一个整数，表示最小的总战斗回合数。

样例输入 复制 

3 3 1 5
6 8 10
3 2
4 3
2 1

样例输出 复制 

4

提示

变量 范围 说明
n 1≤n≤1000 怪物数量
m 0≤m≤1000 升级模块数量
a 1≤a≤104 初始攻击力
E 0≤E≤1000 能量上限
hi 1≤hi≤100 每个怪物血量
uj 1≤uj≤100 模块攻击力加成
cj 1≤cj≤1000 模块能量消耗，总和不超过 E

来源/分类

提交提交记录统计露一手!