U320280 Macw的杭州旅行

这是我来到杭州的第8天，感觉时间过得真快，不一会就临近闭营了。虽然在这段时间里我经历了许多令我难忘的事情，但可惜的是，我没有机会记住大家所有人，因此Macw想出了一个好主意，让大家都记住Macw。（至少这是值得的）。 杭州是一个具有悠久历史的城市，从西湖到天目山无一不是清一色的好景。因此Macw决定过段时间带着他最好的朋友们重返杭州，再次领略这番风景。 这次，Macw和他的朋友们来到了杭州西湖，西湖周边有许多老爷爷老奶奶们在垂钓（提醒：西湖不允许游客私自钓鱼，需要持证钓鱼，千万不要自己去钓鱼，会被罚200元）。Macw07突然对Macw说，我想到了一个搞钱的好办法：“你看这么多人在钓鱼，我们要不去买鱼饲料，这不得赚发？”于是，所有人一拍即合决定向这些在西湖边垂钓的人售卖鱼饲料。 题解：[点我前往](https://www.luogu.com.cn/paste/2mezkdrm)

Macw和他的朋友们从在西湖边行走，途中会遇到了许多家小卖部和因为忘记携带鱼饵而正在苦恼的垂钓者。Macw和他的朋友可以向这些垂钓者们售出一份鱼饵鱼饵（当然这很贵，但垂钓者们又怎么能拒绝呢？）。 同时，Macw和他的朋友们有一个超级大的背包，可以装下无限多的饲料。但是Macw和他的朋友们有一个共同的体力值 $K$，他们每走一个距离单位，他们的体力就会减少自身所携带的饲料的数量。如果他们的体力耗尽了(体力值为0不属于体力值耗尽，体力值耗尽意味体力值小于0)，他们就会被市场监督管理局的人抓住，因为Macw和他的朋友们将鱼饵定价过高。如果Macw和他的朋友被抓住了，这就是一个悲伤的杭州旅行。 Macw和他的朋友们从西湖的东侧向西湖的西侧沿直线前进，路途全长 $L$ 个单位距离。在他们前进的路程中有 $N$ 个小卖部。每隔 $N_i$ 个距离，就会有一家小卖部。在小卖部中，Macw和他的朋友们向小卖部老板购买鱼饲料（鱼饲料的数量是无限的，并且是免费的），同时也可以让他们瞬间恢复满体力值。 此外，在Macw和他的朋友前进的路线中，有 $M$ 个需要鱼饵的垂钓者，这些垂钓者可以选择购买Macw和他的朋友的鱼饵，也可以选择去就近的小卖部购买，但是这些如果正好某个垂钓者距离最近的小卖部的距离为0，他或她会选择去小卖部购买鱼饵而非向Macw一行人购买。 Macw和他的朋友们想知道，当他们完成这一段徒步旅行之后，最多可以卖出多少份鱼饲料？ **备注：** 1. **Macw和他的朋友们一开始没有带任何的鱼饲料。** 2. **Macw和他的朋友们的体力值一开始是满的。** 3. **若垂钓者在终点处，则垂钓者也不会向Macw和他的朋友们购买鱼饵。** 4. **体力值小于0的时候意味体力值耗尽。**

本题有多组输入。一共读入 $3T + 1$ 行数据。\ 第一行读入一个整数 $T$，表示有 $T$ 组输入。 由于本题测试数据很大，请使用c语言的输入输出功能。 **对于每一组输入：** 第一行输入四个数 $L, N, M, K$。分别表整段旅行的距离，小卖部的数量，路途中垂钓者的数量以及Macw和他的朋友们的的体力值。 第二行依次读入 $N$ 个数，表示第 $N_i$ 个小卖部距离Macw出发点的距离，用空格隔开。 第三行依次读入 $M$ 个数，表示第 $M_i$ 垂钓者距离Macw出发点的距离，用空格隔开。

对于每一组测试数据，输出当Macw和他的朋友们完成这一场精美绝伦的旅行后，最多可以卖出多少份鱼饲料。并以换行符换行。 注意： 1. 本题提交答案后不显示分数。 2. **本题不需要使用freopen或fclose，直接正常提交代码即可。** 3. 保证小卖部的坐标不重复。

**文件名：** \ 输入名称：Macw07.in \ 输出名称：Macw07.out **数据范围：**\ $1