题目内容

某工厂现有三种原材料，库存数量分别为 $a, b, c$。利用这些原材料可以组装两种产品：

• 产品一：消耗 $1$ 单位原材料 A 和 $1$ 单位原材料 C，单件利润为 $d$；
• 产品二：消耗 $1$ 单位原材料 B 和 $1$ 单位原材料 C，单件利润为 $e$。

组装需要占用流水线的处理单元。每件产品一占用 $1$ 个单元，每件产品二占用 $2$ 个单元，流水线总共可提供 $r$ 个处理单元。每份原材料至多用于一件产品，允许剩余。

请计算在不超过处理单元限制的前提下，能够获得的最大总利润。

约束：测试数据组数 $T$ 不超过 $10^5$，所有整数 $a, b, c, d, e, r$ 均为非负且不超过 $10^9$。

输入描述

第一行包含一个整数 $T$，表示数据组数。接下来 $T$ 行，每行包含六个整数 $a, b, c, d, e, r$，分别表示原材料 A 的数量、原材料 B 的数量、原材料 C 的数量、产品一的单件利润、产品二的单件利润以及处理单元的总数。

输出描述

对于每组测试数据，输出一行一个整数，表示能够获得的最大总利润。

样例1

输入

3
5 4 6 10 8 10
10 10 3 100 200 100
5 5 5 10 20 3

输出

58
600
30

说明

输入包含 $T=3$ 组数据。

第 1 组：$a=5, b=4, c=6, d=10, e=8, r=10$。约束为 $x \le 5$, $y \le 4$, $x+y \le 6$, $x+2y \le 10$。固定 $y$ 时 $x = \min(5, 6-y, 10-2y)$。枚举 $y \in [0, 4]$：

• $y=0$: $x=5$, 利润 $50$
• $y=1$: $x=5$, 利润 $58$
• $y=2$: $x=4$, 利润 $56$
• $y=3$: $x=3$, 利润 $54$
• $y=4$: $x=2$, 利润 $52$ 最大利润为 $58$。

第 2 组：$a=10, b=10, c=3, d=100, e=200, r=100$。受原材料 C 限制，总产量不超过 $3$。$e > d$，优先生产产品二。当 $y=3$ 时 $x=0$，利润 $600$；其余组合利润均小于 $600$。最大利润为 $600$。

第 3 组：$a=5, b=5, c=5, d=10, e=20, r=3$。处理单元 $r=3$ 严格限制产量：$x+2y \le 3$，且 $y \le \lfloor 3/2 \rfloor =1$。枚举 $y=0,1$：

• $y=0$: $x=\min(5,5,3)=3$, 利润 $30$
• $y=1$: $x=\min(5,4,1)=1$, 利润 $30$ 最大利润为 $30$。

样例2

输入

1
0 3 2 5 3 3

输出

3

说明

输入只有 $T=1$ 组数据：$a=0, b=3, c=2, d=5, e=3, r=3$。由于 $a=0$，无法生产任何产品一，因此 $x$ 必为 $0$。产品二的约束为 $y \le \min(3,2,\lfloor 3/2\rfloor)=1$。取 $y=1$，利润为 $3 \times 1 = 3$。

样例3

输入

1
100 100 100 5 50 10

输出

250

说明

输入只有 $T=1$ 组：$a=100, b=100, c=100, d=5, e=50, r=10$。虽然原材料充足，但处理单元 $r=10$ 成为瓶颈：$x+2y \le 10$，且 $y \le \lfloor 10/2\rfloor=5$。由于 $e \gg d$，应优先生产产品二。$y=5$ 时 $x=\min(100, 95, 0)=0$，利润 $50 \times 5=250$。其他组合均不超过 $250$。最大利润为 $250$。