JSZKC is going to spend his vacation!

His vacation has N days. Each day, he can choose a T-shirt to wear. Obviously, he doesn't want to wear a singer color T-shirt since others will consider he has worn one T-shirt all the time.

To avoid this problem, he has M different T-shirt with different color. If he wears A color T- shirt this day and Bcolor T-shirt the next day, then he will get the pleasure of f[[A][B].(notice: He is able to wear one T-shirt in two continuous days but may get a low pleasure)

Please calculate the max pleasure he can get.

Input Format

The input file contains several test cases, each of them as described below.

• The first line of the input contains two integers N,M (2≤N≤100000,1≤M≤100), giving the length of vacation and the T-shirts that JSZKC has.

• The next follows MM lines with each line MM integers. The j^{th}jth integer in the i^{th}ith line means [i][j] 1≤f[i][j]≤1000000).

There are no more than 1010 test cases.

Output Format

One line per case, an integer indicates the answer.

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <cmath>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 typedef long long ll;

 /*

 f[a][b]+f[b][c]+f[c][d]+……+f[y][z]的最大值。(n-1项)

 n=2 :二重循环

 n=3 :三重循环

 n=4 : f[a][b]+f[b][c]+f[c][d]

 可以用f[a][c]来代替f[a][c]和f[a][b]+f[b][c]的较大值，在进行f[a][c]+f[c][d]

 此时的f[a][c]表示第一天a,第三天c的最大值

 n>=5的依此类推

 那么可以利用矩阵快速幂的思想，因为(n-2)*m^2会超时

 n=2要更新一次来找最大值,n=3就要更新2次。

 因此n要更新n-1次。

 */

 const int  N=;

 ll  f[N][N],n,m;

 struct ma{

     ll m[N][N];

      ma(){

          memset(m,,sizeof(m));

      }

 };

 ll MAX;

 ma poww(ma a,ma  b)

 {

     ma c;

     for(int i=;i<m;i++)

     {

         for(int j=;j<m;j++)

            {

         for(int k=;k<m;k++)

         {

             c.m[i][j]=max(c.m[i][j],a.m[i][k]+b.m[k][j]);

         }

            }

     }

     return c;

 }

 ma qu(ma a,ll n){

     ma c;

     while(n){

         if(n&) c=poww(c,a);

           n>>=;

           a=poww(a,a);

     }

     return c;

 }

 int main()

 {

     while(~scanf("%lld%lld",&n,&m)){

           ma ans;

         for(int i=;i<m;i++)

         {

             for(int j=;j<m;j++)

             {

                 scanf("%lld",&ans.m[i][j]);

             }

         }

         ans=qu(ans,n-);

         MAX=;

         for(int i=;i<m;i++){

             for(int j=;j<m;j++)

             {

                 MAX=max(MAX,ans.m[i][j]);

             }

         }

         printf("%lld\n",MAX);

     }

     return ;

 }