在海滩上,有 $$$n$$$ 小屋排成完美的直线,小屋 $$$1$$$ 位于左侧,小屋 $$$i+1$$$ 位于小屋 $$$i$$$ 右侧 $$$100$$$ 米处,对于所有 $$$1 \le i \le n - 1$$$。小屋里$$$i$$$ 有$$$p_i$$$ 人。
这里有 $$$m$$$ 冰淇淋小贩,也与所有小屋排成一排。第 $$$i$$$ 个冰淇淋卖家的商店位于第一个小屋右侧 $$$x_i$$$ 米处。所有冰淇淋店都位于不同的位置,但它们可能与小屋位于同一位置。
您想开一家新冰淇淋店,并且想知道您的店的最佳位置在哪里。您可以将冰淇淋店放置在海滩上的任何位置(不一定距第一个小屋为整数距离),只要它与小屋和其他冰淇淋店对齐即可,即使该位置已经有另一家冰淇淋店或小屋。您知道,只有当您的店比任何其他冰淇淋店更靠近他们的小屋时,人们才会来您的店。
如果住在小屋里的每个人都想买一份冰淇淋,那么如果您对商店进行最佳布局,您最多可以出售多少冰淇淋?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — 小屋的数量和冰淇淋卖家的数量。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 10^9$$$) — 每个小屋中的人数。
第三行包含 $$$m$$$ 整数 $$$x_1, x_2, \ldots, x_m$$$ ($$$0 \le x_i \le 10^9$$$, $$$x_i \ne x_j$$$ for $$$i \ne j$$$) — 每个冰淇淋店的位置。
输出
打印通过选择新商店的最佳位置可以出售的冰淇淋的最大数量。
示例
输入 #1
3 1 2 5 6 169
输出 #1
7
输入 #2
4 2 1 2 7 8 35 157
输出 #2
15
输入 #3
4 1 272203905 348354708 848256926 939404176 20
输出 #3
2136015810
输入#4
3 2 1 1 1 300 99
输出#4
2
注意
在第一个示例中,您可以将商店(下图中的橙色)$$$150$$$ 米放置在第一个小屋的右侧(例如),这样它就是距离前两个小屋最近的商店,前两个小屋有 $$$2$$$ 和 $$$5$$$ 人,总共售出 $$$7$$$ 冰淇淋。
在第二个示例中,您可以将商店 $$$170$$$ 米放置在第一个小屋的右侧(例如),以便它是距离最后两个小屋最近的商店,最后两个小屋有 $$$7$$$ 和 $$$8$$$ 人,总共售出 $$$15$$$ 冰淇淋。