小红打怪
题号：NC254195
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

已知地图上有 n 只怪物，每只怪物的血量是 a_i ，攻击力是 b_i。小红准备去地图上探险杀怪，她的初始血量为 h。
小红有两个技能：
1. 普通攻击：对一只怪物造成1点伤害。
2. 强力攻击：对一只怪物造成2点伤害。
但是强力攻击是有冷却时间的。释放一个强力攻击后，需要2回合冷却（即释放2次普通攻击后）才能再次释放。
小红每次攻击后，若怪物没有死亡（即血量大于0），小红都会承受一次怪物攻击力的伤害。但是小红可以在战斗开始前喝血药，每个血药可以回复 k 点血量。也就算说， x 瓶血药可以将小红的初始血量提高到 
已知每只怪物都是不可复活的，当小红血量为0或负数时死亡。小红选择打一个怪时，在该怪物被打死之前不会更换目标。
当小红打死一只怪物去寻找另外一只怪物的过程中，我们可以认为强力攻击的冷却已经恢复完毕。
请问，小红初始带了 x 瓶血药时，最多可以击杀多少只怪物？
上述问题会重复 q次，每次询问都是独立的，小红初始的血瓶数量可能不同。

输入描述:

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

输出描述:

输出一行 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瓶血药时，可以击杀第一只、第三只怪物。