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.*;

public class Spoj {

    static int arr[]=new int[10001];
    static int count[]=new int[301];
    static int LIS(int n){
        int lis[]=new int[n+1];
        Arrays.fill(lis, 1);
        int ans=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++)
                if(arr[j]<=arr[i])
                    lis[i]=Math.max(lis[j]+1, lis[i]);
            ans=Math.max(ans, lis[i]);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),t=in.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=in.nextInt();
            count[arr[i]]++;
        }
        for(int i=n+1;i<=Math.min(n, t)*n;i++)
            arr[i]=arr[i-n];
        int ans=LIS(Math.min(n,t)*n);
        if(n>=t){
            System.out.println(ans);
        }
        else{
            int cmax=0;
            for(int i=1;i<=300;i++)
                cmax=Math.max(cmax, count[i]);
            System.out.println((ans+(t-n)*cmax));
        }
        in.close();
    }
}
