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 OnceAgain
{

	static int oo = Integer.MAX_VALUE/3;
	static int[] arr;

	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		arr = new int[n];
		for(int i = 0; i < n; i++) arr[i] = scan.nextInt();

		long[][] T = new long[n][n];

		for(int s = 0; s < n; s++) {
			for(int e = 0; e < n; e++) {
				if(arr[e] >= arr[s]) {
					T[s][e] = 1;
					for(int i = 0; i < e; i++) {
						if(arr[e] >= arr[i]) {
							T[s][e] = Math.max(T[s][e], T[s][i]+1);
						}
					}
				}
				else T[s][e] = -oo;
			}
		}
		T = matPow(T, k);
		long ans = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				ans = Math.max(ans, T[i][j]);
			}
		}
		System.out.println(ans);

	}

	static long[][] matPow(long[][] A, long p){
		if(p == 1) 
			return A;
		if(p % 2 == 1) {
			long[][] B = matPow(A, p-1);
			return multiply(B, A);
		}
		long[][] B = matPow(A, p/2);
		return multiply(B, B);
	}

	static long[][] multiply(long[][] A, long[][] B){
		long[][] res = new long[A.length][B[0].length];
		if(A[0].length != B.length) System.out.println("Invalid multiplication");
		for(int i = 0; i < A.length; i++) {
			for(int j = 0; j < B[0].length; j++) {
				res[i][j] = -oo;
				if(arr[j] >= arr[i]) {
					for(int k = 0; k < B.length; k++) {
						
						res[i][j] = Math.max(res[i][j], (A[i][k]+B[k][j]));
					}
				}
			}
		}
		return res;
	}
}
