题目描述

上学期期末推迟至本学期

\(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\)