Description

植物大战僵尸这款游戏中，还有一个特别的玩儿法:玩家操纵僵尸进攻植物。首先，僵尸有m(m<=100)种(每种僵尸都是无限多的)，玩家可以选择合适的僵尸来进攻。使用第i种僵尸需要花费Wi资源，可以得到Pi的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。

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

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

Format

Input

第一行二个非负整数:m、n;

第二行m个正整数，第i个数表示Wi，每种僵尸花费的资源;

第三行m个正整数，第i个数表示Pi，每种僵尸的攻击效果;

第四行n个非负整数，第i个数表示Qi，每行植物被攻破所需的Qi；

Output

一个正整数k

Samples

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

32

Sample Explanation

需要的最小代价是16+5+4+7=32