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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class B582 {
    public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = inp.readLine().split(" ");
        int size = Integer.parseInt(s1[0]);
        int multi = Integer.parseInt(s1[1]);
        String[] s2 = inp.readLine().split(" ");
        int[] given = new int[size];
        int[] givenCopy = new int[2*size];
        int times = 100;
        int[] givenCopyCopy = new int[times*size];
        int maxCopy = 1;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<size;i++){
            int a = Integer.parseInt(s2[i]);
            given[i] = a;
            givenCopy[i] = a;
            givenCopy[i+size] = a;
            for(int j=0;j<times;j++){
                givenCopyCopy[i+j*size] = a;
            }
            if(map.containsKey(a)){
                int z = map.get(a);
                map.remove(a);
                z++;
                map.put(a,z);
                maxCopy = Math.max(maxCopy,z);
            }
            else{
                map.put(a,1);
            }
        }
        if(multi>1){
            if(multi>=100){
                int a = solve(givenCopyCopy,100*size);
                //System.out.println(maxCopy);
                System.out.println(a+((multi-100)*maxCopy));
            }
            else{
                int a = solve(givenCopyCopy,multi*size);
                System.out.println(a);
            }

        }
        else{
            int a = solve(given,size);
            System.out.println(a);
        }
    }
    static int solve(int[] given,int size){
        int[] dp = new int[size];
        dp[0] = 1;
        int max = 1;
        for(int i=1;i<size;i++){
            dp[i] =1;
            for(int j=0;j<i;j++){
                if(given[i]>=given[j]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                    max = Integer.max(dp[i],max);
                }
            }
        }
        //print(dp);
        return max;

    }
    static void print(int[] a){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

}
