该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小红打怪

链接：https://ac.nowcoder.com/acm/contest/60456/D
来源：牛客网

时间限制：C/C++ 1秒
空间限制：C/C++ 262144K

题目描述

已知地图上有 \(n\) 只怪物，每只怪物的血量是 \(a_i\) ，攻击力是 \(b_i\)。小红准备去地图上探险杀怪，她的初始血量为 \(h\)。
小红有两个技能：

1. 普通攻击：对一只怪物造成1点伤害。

2. 强力攻击：对一只怪物造成2点伤害。

但是强力攻击是有冷却时间的。释放一个强力攻击后，需要2回合冷却（即释放2次普通攻击后）才能再次释放。
小红每次攻击后，若怪物没有死亡（即血量大于0），小红都会承受一次怪物攻击力的伤害。但是小红可以在战斗开始前喝血药，每个血药可以回复 \(k\) 点血量。也就算说，\(x\) 瓶血药可以将小红的初始血量提高到 \(h+x*k\)

已知每只怪物都是不可复活的，当小红血量为0或负数时死亡。小红选择打一个怪时，在该怪物被打死之前不会更换目标。

当小红打死一只怪物去寻找另外一只怪物的过程中，我们可以认为强力攻击的冷却已经恢复完毕。

请问，小红初始带了 \(x\) 瓶血药时，最多可以击杀多少只怪物？

上述问题会重复 \(q\) 次，每次询问都是独立的，小红初始的血瓶数量可能不同。

输入描述:

第一行输入三个正整数 \(n,h,k\) ，代表地图上怪物的数量、小红的初始血量，以及小红每瓶血药可以回复的血量。
接下来的 \(n\) 行，每行输入两个正整数 \(a_i\) 和 \(b_i\)，代表地图上每只怪物的血量和攻击力。
接下来的一行输入一个正整数 \(q\)，代表询问次数。
接下来的一行，输入 \(q\) 个正整数 \(x\)，代表每次询问中小红携带的血药数量。
\(1\leq n,q,h,k,a_i,b_i,x \leq 10^5\)

输出描述:

输出一行 \(q\) 个正整数，代表小红携带 \(x\) 瓶血药时能击杀的最多怪物数量。

示例1

输入

3 1 2
5 1
5 2
3 2
3
1 2 3

输出

1 1 2

说明

第一只怪物小红需要攻击4次才能杀死，所以会被怪物打3下，掉血为\(1*3=3\)。
第二只怪物小红需要攻击4次才能杀死，所以会被怪物打3下，掉血为\(2*3=6\)。
第三只怪物小红需要攻击2次才能杀死，所以会被怪物打1下，掉血为\(2*1=2\)。
当小红携带1瓶血药时，可以先将血量回复至3点，然后击杀第三只怪物，剩余血量为1。
当小红携带2瓶血药时，无法击杀两只怪物。
当小红携带3瓶血药时，可以击杀第一只、第三只怪物。