题目描述

三人组队比赛即将开启！作为一名选手，你很希望自己拿到好成绩，为此，你需要在人群中n个人里面找到两位作为你的队友。而在未来一共m场比赛，你可以选择其中一场，和你的队友一起参与。

对于n个人，每个人的实力由一个公式决定，实力=成长系数*天数+初始实力，n个人的成长系数和初始实力都会告诉你，你可以任意选择两名作为你的队友。

对于m场比赛，每个比赛会告知你它在哪一天举办，你可以选择其中任意一场。

请做出最好的选择，得到你可能在比赛中最强的队友战力之和。

注：有人训练勤奋，有人相反，故成长系数取值可为负数，且为了方便计算，我们认为实力和初始实力也可为负数。

输入格式

输入共四行。 第一行输入$n,m$，分别表示选手数量和比赛数量。

第二行输入$k_i$，表示第i个选手的成长系数

第三行输入$b_i$，表示第i个选手的初始实力

第四行输入$t_i$，表示第i场比赛的时间，即天数。

输出格式

输出一行，表示答案

样例

3 3
2 0 -1
4 5 8
1 3 5

19

样例1解释： 我们可以选择第1和第2个选手作为我们的队友，再选择第三场比赛，队友的战力之和为$(2*5+4)+(0*5+5)$，总之为19，为我们可以得到的最高战斗力

限制

1s, 256mb

数据范围

对于30%的数据，$2\leq{n}\leq{100},1\leq{m}\leq{100},{|k|,|b|}\leq{100},1\leq{t}\leq{100}$

对于另外30%的数据，$2\leq{n}\leq{100},1\leq{m}\leq{10^5},{|k|,|b|}\leq{10^9},1\leq{t}\leq{10^9}$

对于100%的数据，$2\leq{n}\leq{10^5},1\leq{m}\leq{10^5},{|k|,|b|}\leq{10^9},1\leq{t}\leq{10^9}$