You are given an array of positive integers a1, a2, ..., an × T of length n × T. We know that for any i > n it is true that ai = ai - n. Find the length of the longest non-decreasing sequence of the given array.

Input

The first line contains two space-separated integers: n, T (1 ≤ n ≤ 100, 1 ≤ T ≤ 107). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 300).

Output

Print a single number — the length of a sought sequence.

Examples

Input

4 3
3 1 4 2


Output

5

Note

The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence. 
import java.util.Scanner;

/**
 * Created by slycer on 10/3/15.
 */
public class OnceAgain {

    public static void main ( String [] args ){
        Scanner s = new Scanner( System.in );
        int n = s.nextInt();
        int t = s.nextInt();
        int [] data = new int[n];
        int [] count = new int[301];
        for ( int i=0; i<n; i++ ){
            data[i] = s.nextInt();
            count[data[i]]++;
        }

        int [] dp = new int[301];

        int sol = 0;
        int prevSol = 0;
        int increment = 0;
        for ( int i=0; i<Math.min(t,300); i++ ){
            for ( int j=0; j<data.length; j++ ){
                for ( int k=data[j]; k>=0; k-- ){
                    dp[data[j]] = Math.max( dp[data[j]], dp[k]+1);
                }
                sol = Math.max( sol, dp[data[j]] );

               // System.out.print( dp[data[j]] + " " );
            }
            increment = sol - prevSol;
            prevSol = sol;
            //System.out.println( sol  );
            //System.out.println();
        }

        sol += increment * Math.max(0,t-300);

        System.out.println( sol );

    }

}
