J17 实践-4 僵尸的进攻

题目描述

植物大战僵尸这款游戏中，还有一个特别的玩儿法：玩家操纵僵尸进攻植物。

首先，僵尸有 $m$ 种（每种僵尸都是无限多的），玩家可以选择合适的僵尸来进攻。使用第 $i$ 种僵尸需要花费 $W_i$资源，可以得到 $P_i$ 的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。

地图共有 $n$ 行，对于第 $i$ 行，最左端有若干植物，这些植物需要至少 $Q_i$ 的攻击才能被全部消灭。若一行上的植物全部被消灭，我们称这一行被攻破。

由于资源紧张，我们希望能够算出攻破所有行总共需要的最少的资源值 $K$，你能算出 $K$ 值来吗？

输入格式

第一行两个非负整数：$m$,$n$；

第二行 $m$ 个正整数，第 $i$ 个数表示 $Wi$；

第三行 $m$ 个正整数，第 $i$ 个数表示 $P_i$；

第四行 $n$ 个非负整数，第 $i$ 个数表示 $Q_i$。

输出格式

一个正整数K。

样例输入

3 4
5 2 11
3 1 7
10 3 2 4

样例输出

32

样例分析

样例说明：需要的最小代价是 $16+5+4+7=32$。

数据范围

对于 $100\%$ 的数据：$m \le 100$ ，$n \le 200000$，$q \le 200000$。