题目描述

有 $n$ 个怪物排成一行，编号从 $1$ 到 $n$。第 $i$ 个怪物有 $h_i$ 点生命值（hp）。你的攻击力为 $a$，你的对手的攻击力为 $b$。

你和你的对手将一起与这些怪物战斗。首先，你们一起去攻击第一个怪物，直到它死亡，然后再一起去攻击第二个怪物，依此类推。当怪物的生命值小于等于 $0$ 时，视为死亡。

与每个怪物的战斗是轮流进行的。

1. 你先攻击怪物，造成 $a$ 点伤害。如果你的攻击后怪物死亡，你获得 $1$ 分，然后你们一起前往下一个怪物。
2. 如果怪物还活着，你的对手攻击怪物，造成 $b$ 点伤害。如果对手的攻击后怪物死亡，则没有人得分，然后你们一起前往下一个怪物。

你有一种秘密技巧，可以让你的对手跳过他的回合。你最多可以在所有怪物中总共使用 $k$ 次这种技巧（例如，如果有两个怪物且 $k=4$，你可以在第一个怪物上用 $2$ 次，在第二个怪物上用 $1$ 次，但不能在第一个怪物上用 $2$ 次，在第二个怪物上用 $3$ 次）。

你的任务是，若你最优地使用秘密技巧，求你最多能获得多少分。

输入格式

输入的第一行包含四个整数 $n, a, b, k$（$1 \le n \le 2 \times 10^5, 1 \le a, b, k \le 10^9$），分别表示怪物的数量、你的攻击力、对手的攻击力以及你可以使用秘密技巧的次数。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^9$），其中 $h_i$ 表示第 $i$ 个怪物的生命值。

输出格式

输出一个整数，表示你在最优使用秘密技巧的情况下最多能获得的分数。

说明/提示

由 ChatGPT 4.1 翻译

样例

6 2 3 3
7 10 50 12 1 8

5

1 1 100 99
100

1

7 4 2 1
1 3 5 4 2 7 6

6