题目描述

上学期期末推迟至本学期

$n$ 天的考试期举行 $m$ 场考试，每天可以考 $a_i$ 门，每门课要改出来需要 $t_i$ 天。

学生们对每门课的仇恨值是 $h_i$，他们当然希望每门课越晚越被改出来。当他们在考试期结束后第 $x$ 天知道第 $i$ 科的成绩，他们的快乐值会增加 $x \times h_i$ 。请你规划考试时间安排，使学生的快乐值最大。

PS: 老师们很良心，他们不会在所有考试没结束的时候告诉你成绩，如果某一门科目在考试期间被改出来了，你会在考试期结束当天后一天早上被告知成绩。

输入格式

$n$ $m$

$a_1$ , $a_2$ , $a_3$ , $......$ , $a_n$

$t_1$ , $t_2$ , $t_3$ , $......$ , $t_m$

$h_1$ , $h_2$ , $h_3$ , $......$ , $h_m$

输出格式

最大快乐值

样例

样例输入 1

3 6
2 2 2
2 1 1 2 5 1
5 4 1 3 100 2

样例输出 1

520

提示说明

在第一天安排第二门和第三门

在第二天安排第四门和第六门

在第三天安排第一门和第五门

则考完试后：

第一天出第二三四六门

第二天出第一门

第五天出第五门

对于 $30 \%$的数据

$m \le 10$

对于 $60 \%$ 的数据

$m \le 2000$

对于 $100\%$ 的数据

$m \le 2 \times 10^5$

$a_i > 0$

$a_1+a_2+a_3.......a_n=m$

$h_i,t_i< 10^9$