U28057.再战雷霆峡谷-提升版

$k$ 有一个最大可以容纳 $m$ 大小的背包，在雷霆峡谷中又发现一片区域有 $n$ 种无限量水晶，每种水晶的重量是 $w_1, w_2, ...,w_m$，同时每种水晶的价值各有千秋 $v_1, v_2, ..., v_m$，$k$ 仔细一看，发现每种水晶只能使用有限的个数，不然装入背包会产生水晶裂变，将其他水晶都震碎了，每种水晶的使用数量 $c_1,c_2,...,c_m$。

请问，装入背包内（背包不一定需要装满）的水晶最大价值可以是多少？

第一行两个整数 $n, m$。

第二行是每种水晶的重量，总共有 $n$ 个整数。

第三行是每种水晶的价值，总共有 $n$ 个整数。

第四行是每种水晶最大可以收集的数量，总共有 $n$ 个整数。

---

• $1\leq n\leq 10^4$
• $1\leq m\leq 4\times 10^4$
• $1\leq w_i \leq 10^4$
• $1\leq v_i\leq 10^7$
• $n\leq \sum{c_i}\leq 10^5$

装入背包内水晶的最大价值。