###### tags: `APCS` `c++` `DP`
# 題解 zerojudge i402: 4. 內積 APCS
### DP[i][j]存A[i]*B[i]

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005]={0},r_dp[1005][1005]={0};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,ans=-100000;
    cin>>n>>m;
    int A[1005]={0},B[1005]={0};
    for(int i=0;i<n;i++)    cin>>A[i];
    for(int i=0;i<m;i++)    cin>>B[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)    {dp[i][j]=A[i]*B[j];r_dp[i][j]=A[i]*B[(m-j-1)];}
    }
    int x,y,now;
    for(int i=0;i<n;i++){
        x=i;y=0;now=0;
        while(x<n and y<m){
            now+=dp[x][y];
            ans=max(ans,now);
            if(now<0)  now=0;
            x++;y++;
        }
        x=i;y=0;now=0;
        while(x<n and y<m){
            now+=r_dp[x][y];
            ans=max(ans,now);
            if(now<0)  now=0;
            x++;y++;
        }
    }
    for(int i=0;i<m;i++){
        x=0;y=i;now=0;
        while(x<n and y<m){
            now+=dp[x][y];
            ans=max(ans,now);
            if(now<0)  now=0;
            x++;y++;
        }
        x=0;y=i;now=0;
        while(x<n and y<m){
            now+=r_dp[x][y];
            ans=max(ans,now);
            if(now<0)  now=0;
            x++;y++;
        }
    }
    cout<<ans;
}