UOJ Logo Universal Online Judge

UOJ

统计

要过年了!《蓝猫淘气三千问》里的淘气决定囤积一些好吃的以完成“每逢佳节胖十斤”的计划。然而,超威蓝猫早就把他之前的大米都偷吃完了,淘气只好出门买一些。

这天,淘气带着 $m$ 块钱来到了一家有 $n$ 袋大米正在出售的商店。这 $n$ 袋大米的编号依次为 $1, \dots, n$,其中第 $i$ 袋大米的重量为 $w_i$,价格为 $p_i$。

正当淘气觉得价格太贵准备走的时候,老板突然告诉他:这家商店正在进行年底促销,有两种促销方式!

  1. 买 $a$ 赠一:每买 $a$ 袋大米,即可白送一袋没有买的大米;
  2. 买 $b$ 赠一:每买 $b$ 袋大米,即可白送一袋没有买的大米。

不仅如此,这两种促销方式还可以同时使用。也即,如果淘气如果买了 $k$ 袋大米,那么他就可以在剩下的没有买的大米中,挑至多 $\lfloor k/a \rfloor + \lfloor k/b \rfloor$ 袋免费拿走(其中$\lfloor x \rfloor$ 表示小于等于 $x$ 的最大的整数)。

现在淘气想知道,对于每一个 $1 \le j \le m$,在花费至多 $j$ 块钱的情况下,从商店买走或免费拿走的大米总重量最大是多少。

输入格式

第一行四个正整数 $n, m, a, b$。保证 $1 \le a \le b \le n$。

第二行包含 $n$ 个正整数,分别表示 $w_1, \dots, w_n$。

第三行包含 $n$ 个正整数,分别表示 $p_1, \dots, p_n$。保证 $1 \le p_i \le m$。

输出格式

一行,包含 $m$ 个整数。其中第 $j$ 个整数表示在花费至多 $j$ 块钱的情况下,从商店买走或免费拿走的大米的最大总重量。

样例一

input

8 4 1 2
4 5 3 2 6 7 3 1
2 2 2 2 2 2 2 2

output

0 13 13 25

explanation

  • 如果淘气只花一块钱,那么什么都买不到。
  • 如果淘气花两块钱,那么淘气可以买下重量为 $7$ 的大米,然后利用 “买一赠一” 拿走一袋重量为 $6$ 的大米。
  • 如果淘气花四块钱,那么淘气可以买下重量为 $4$ 和 $5$ 的大米,然后利用 “买一赠一” 和 “买二赠一” 拿走三袋重量分别为 $3, 6, 7$ 的大米。

样例二

input

10 15 3 3
9 9 2 6 9 7 6 2 8 5
6 2 2 2 9 2 8 7 3 2

output

0 9 9 16 17 40 42 45 48 48 53 53 63 63 63

explanation

在这个例子里,$a = b = 3$,也就是 “买三赠二”。淘气可买下的米的重量随着花的钱数递增。当淘气可以花 $13$ 块钱的时候,淘气可以买走第 $2, 3, 4, 6, 9, 10$ 号大米,然后免费拿走剩下的大米。

样例三

见“样例数据下载”

限制与约定

测试点编号$n$$m$特殊限制
$1$$\le 10$$\le 150$
$2$
$3$$\le 50$
$4$
$5$
$6$
$7$$\le 300$$\le 1000$$a = b$
$8$
$9$
$10$

对于所有数据,保证 $1 \le w_i \le 10^6$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载