很深刻的题啊。

这种问题肯定不能直接去 dp，状态太多了。

不妨先从更简单的局面开始思考。

假设 $(a,b),(i,j)$ 为最优路径上的两个拐点（或起点、终点），并且钦定 $(i,j)$ 是由 $(a,b)$ 经过一条 $L$ 型的路径到达的，也就是这种情况：

$(i,j)$ 只能通过 $(a,b)$ 走红色路径或蓝色路径到达。

接着我们考虑什么时候会走红色，什么时候会走蓝色。

红色路径的代价：$(i-x)b_y+(j-y)a_i$；

蓝色路径的代价：$(j-y)a_x+(i-x)b_j$。

经过推导后我们容易得到红色比蓝色优的条件：

可以发现行和列已经完全独立。

我们考虑在 $x$ 时，求出一个 $i$，使得 $\frac{a_i-a_x}{i-x}$ 最小，$y$ 同样找到一个 $j$，然后看红色优还是蓝色优，并跳到更优的那个 $i$ 或是 $j$。容易发现这样一定是不劣的。

所以我们只用维护两个凸壳，分别对应行和列，每次跳到更优的位置即可，贡献时好算的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1e5+5;
int n,m;
int a[Maxn],b[Maxn];
inline bool check(int p,int q,int p1,int q1){return p*q1>p1*q;}
struct tubao{
	int stk[Maxn],len;
}A,B;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		while(A.len>=2&&check(a[A.stk[A.len]]-a[A.stk[A.len-1]],A.stk[A.len]-A.stk[A.len-1],a[i]-a[A.stk[A.len]],i-A.stk[A.len]))A.len--;
		A.stk[++A.len]=i;
	}
	for(int i=1;i<=m;i++){
		b[i]=read();
		while(B.len>=2&&check(b[B.stk[B.len]]-b[B.stk[B.len-1]],B.stk[B.len]-B.stk[B.len-1],b[i]-b[B.stk[B.len]],i-B.stk[B.len]))B.len--;
		B.stk[++B.len]=i;
	}
	int p1=1,p2=1,res=0;
	while(p1<A.len||p2<B.len){
		if(p1>=A.len||(p2<B.len&&check(a[A.stk[p1+1]]-a[A.stk[p1]],A.stk[p1+1]-A.stk[p1],b[B.stk[p2+1]]-b[B.stk[p2]],B.stk[p2+1]-B.stk[p2]))){
			res+=(B.stk[p2+1]-B.stk[p2])*a[A.stk[p1]];
			p2++;continue;
		}
		if(p2>=B.len||(p1<A.len&&!check(a[A.stk[p1+1]]-a[A.stk[p1]],A.stk[p1+1]-A.stk[p1],b[B.stk[p2+1]]-b[B.stk[p2]],B.stk[p2+1]-B.stk[p2]))){
			res+=(A.stk[p1+1]-A.stk[p1])*b[B.stk[p2]];
			p1++;continue;
		}
	}
	printf("%lld\n",res);
	return 0;
}