Travel

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4353		Accepted: 1817

Description

One traveler travels among cities. He has to pay for this while he can get some incomes.

Now there are n cities, and the traveler has m days for traveling. Everyday he may go to another city or stay there and pay some money. When he come to a city ,he can get some money. Even when he stays in the city, he can also get the next day's income. All the incomes may change everyday. The traveler always starts from city 1.

Now is your turn to find the best way for traveling to maximize the total income.

Input

There are multiple cases.

The first line of one case is two positive integers, n and m .n is the number of cities, and m is the number of traveling days. There follows n lines, one line n integers. The j integer in the i line is the expense of traveling from city i to city j. If i equals to j it means the expense of staying in the city.

After an empty line there are m lines, one line has n integers. The j integer in the i line means the income from city j in the i day.

The input is finished with two zeros.

n,m<100.

Output

You must print one line for each case. It is the max income.

Sample Input

3 33 1 22 3 11 3 22 4 34 3 23 4 20 0

Sample Output

8

Hint

In the Sample, the traveler can first go to city 2, then city 1, and finish his travel in city 1. The total income is:

-1+4-2+4-1+4=8;

挺简单的，，但是又坑在初始化了，，

题意：题目有点绕,输入n,m n代表城市数,m代表天数

然后是一个 n*n的矩阵 expense[i][j]代表从第i个城市到第j个城市的花费

然后是一个 m*n的矩阵 income[i][j]代表第i天在第j个城市的收入.

分析:dp[i][j]代表第i天在第j个城市前i天能够获得的最大income（income可能为负）

那么 dp[i][j] = max(dp[i][j],dp[i-1][k]-express[k][i]+income[i][j])

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=105;int express[N][N];int income[N][N];int dp[N][N];int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF,n+m){        for(int i=1;i<=n;i++){            for(int j=1;j<=n;j++){                scanf("%d",&express[i][j]);            }        }        for(int i=1;i<=m;i++){            for(int j=1;j<=n;j++){                scanf("%d",&income[i][j]);            }        }        for(int i=1;i<=n;++i)            dp[0][i]=-1000000000;        dp[0][1]=0;///初始化第0天在第1个城市为0        for(int i=1;i<=m;i++){ ///枚举天数            for(int j=1;j<=n;j++){ ///枚举第i天                dp[i][j]=dp[i-1][1]+income[i][j]-express[1][j];                for(int k=1;k<=n;k++){ ///枚举i-1天                    dp[i][j]=max(dp[i][j],dp[i-1][k]-express[k][j]+income[i][j]);                }            }        }        int ans = -99999999999;        for(int i=1;i<=n;i++){            ans = max(ans,dp[m][i]);        }        printf("%d\n",ans);    }    return 0;}