1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string.h>

 5 #include<stdlib.h>

 6 typedef long long LL;

 7 LL dp[1005][1005];

 8 LL a[1005][1005];

 9 using namespace std;

10 int main(void)

11 {

12     int n,i,j,k,p,q;

13     while(scanf("%d %d",&p,&q)!=EOF)

14     {

15         for(i=1; i<=p; i++)

16         {

17             for(j=1; j<=q; j++)

18             {

19                 scanf("%lld",&a[i][j]);

20             }

21         }

22         memset(dp,0,sizeof(dp));

23         for(i=1; i<=p; i++)//初始化边界当j为1时，dp[i][j]只能从dp[i-1][1]转移而来

24         {

25             if((i+1)%2==1)

26             {

27                 dp[i][1]=dp[i-1][1]+a[i][1]*a[i-1][1];

28             }

29             else dp[i][1]=dp[i-1][1];

30         }

31

32         for(i=1; i<=q; i++)//初始化边界当i为1时，dp[i][j]只能从dp[1][j-1]转移而来

33         {

34             if((i+1)%2==1)

35             {

36                 dp[1][i]=dp[1][i-1]+a[1][i-1]*a[1][i];

37             }

38             else dp[1][i]=dp[1][i-1];

39         }

40         for(i=2; i<=p; i++)

41         {

42             for(j=2; j<=q; j++)

43             {

44                 if((i+j)%2==1)

45                     dp[i][j]=min(dp[i-1][j]+a[i][j]*a[i-1][j],dp[i][j-1]+a[i][j-1]*a[i][j]);

46                 else dp[i][j]=min(dp[i-1][j],dp[i][j-1]);

47             }

48         }

49         printf("%d\n",dp[p][q]);

50     }

51     return 0;

52 }