SP15827 AUT - Vending Machine

Byteasar 是 Bytetown 大学计算机科学系的一名学生。他们系里有一台出售零食的自动售货机，可以买到 $n$ 种不同类型的零食，这些零食以 $1$ 到 $n$ 的编号标识。各类零食的价格不同，因为它们在尺寸和口味上存在差异。 最近，Byteasar 发现该售货机出现了故障。当购买第 $i$ 类零食时，售货机会额外吐出第 $1$ 到第 $i-1$ 类的每种零食各一份（如果这些类型还有库存的话）。如果某一类型第 $1$ 到第 $i-1$ 类的零食已经售罄，该类型零食就不会发放。只有当第 $i$ 类零食至少还有一个时，才可以购买该类型的零食。 Byteasar 想借此机会最大化他能用手头上资金购买零食的总价值，即总价格。他并不要求使用全部预算。

第一行为整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行为两个整数 $n$ 和 $k$（$1 \le n \le 40$，$1 \le k \le 64000$），分别代表零食的种类数和 Byteasar 拥有的总金钱数。第二行为 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 40$），表示每种零食的单价。第三行为 $n$ 个整数 $l_1, l_2, \ldots, l_n$（$1 \le l_i \le 40$），表示售货机中各类零食的库存数量。

对于每个测试用例，输出一个整数，表示 Byteasar 在不超过 $k$ 单位资金的情况下，能从售货机中获得的零食的最大总价值。 **本翻译由 AI 自动生成**