压岁钱__牛客网

除夕之夜，爆竹声中一岁除。小红正坐在年夜饭桌旁，一边品尝着热气腾腾的饺子，一边盯着手机里的微信群。长辈们在这个时刻最喜欢在不同的亲友群里发放红包。就在此时，时钟已经走向了深夜，距离零点的钟声敲响只剩下 $t$ 秒。为了辞旧迎新，小红希望在零点之前尽可能多地收集《压岁钱》。

手机里一共有 $n$ 个亲友红包群。对于每个红包群 $i$ ，里面都有 $a_i$ 个待领取的红包，且由于长辈们发得比较平均，该群里的每个红包金额都是 $b_i$ 元。然而，领取这些红包是需要时间的：
1. 如果小红决定从第 $i$ 个群里领取红包（无论领取几个），她首先需要花费 $x$ 秒的固定时间切换进这个群。
2. 在进入第 $i$ 个群后，每拆开一个红包都需要额外花费 $y$ 秒的时间。
3. 如果小红不在某个群领红包，则不需要花费任何时间在该群上。

小红希望在总时间不超过 $t$ 秒的前提下，能够收集到总金额最高的压岁钱。请你帮她计算出这个最高金额，并告诉她在每个群分别领取了多少个红包。

输入仅包含一组测试数据。
第一行包含四个整数 $n, x, y, t$ ( $1 \leqq n \leqq 100$ ， $0 \leqq x, y \leqq 1000$ ， $1 \leqq t \leqq 2000$ )，分别表示红包群的数量、进入每个群的固定时间、拆开一个红包所需的时间，以及总的时间限制。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \leqq a_i \leqq 100$ )，表示每个红包群中的红包数量。
第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ( $1 \leqq b_i \leqq 1000$ )，表示每个红包群中单个红包的金额。

说明


	在样例中，总共有 5 秒时间。进入任何一个群需 1 秒，拆开一个红包需 2 秒。

	- 红包群 1：有 3 个红包，每个 1 元。

	- 红包群 2：有 2 个红包，每个 5 元。

	- 红包群 3：有 3 个红包，每个 3 元。


	策略：

	1. 不进入红包群 1（耗时 0 秒，获得 0 元）。

	2. 进入红包群 2 并拆开 2 个红包。耗时 =  秒。获得金额 =  元。

	3. 不进入红包群 3（耗时 0 秒，获得 0 元）。


	此时总耗时为 5 秒，总金额为 10 元，这是能获得的最高金额。输出 `0 2 0` 代表分别从三个群取出的红包数量。

压岁钱

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题