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[] arr3;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int[] arr = new int[N];
		arr3 = new int[2*N];
		int M = T % N;
		int[] arr2 = new int[M];
		for (int i = 0; i < arr.length; i++) {
			if (i < N) {
				arr[i] = sc.nextInt();
			} else {
				arr[i] = arr[i-N];
			}
			if (i < M) {
				arr2[i] = arr[i];
			}
		}
		for (int i = 0; i < arr.length; i++) {
			arr3[i+N] = arr[i];
			arr3[i] = arr[i];
		}
		int[] valsStart = new int[arr.length];
		//longest increasing starting at i
		int[] valsEnd = new int[arr.length];
		//longest increasing ending at i
		Arrays.fill(valsStart, 1);
		Arrays.fill(valsEnd, 1);
		int maxx = 1;
		for (int i = arr.length-1; i >= 0; i--) {

			for (int j = i+1; j < arr.length; j++) {
				if (arr[i] <= arr[j]) {
					valsStart[i] = Math.max(valsStart[i], 1+valsStart[j]);
					maxx = Math.max(maxx, valsStart[i]);
				}
			}
		}
		for (int i = 0; i < arr.length; i++) {
			for (int j = i+1; j < arr.length; j++) {
				if (arr[i] <= arr[j]) {
					valsEnd[j] = Math.max(valsEnd[j], 1+valsEnd[i]);
				}
			}
		}
		if (T == 1) {
			System.out.println(maxx);
			return;
		}
		//System.out.println(Arrays.toString(valsStart));
		//System.out.println(Arrays.toString(valsEnd));
		//if (M == 0) {
		//	System.out.println(max);
		//} else {
			//Match ends to starts
			long max = 0;
			fromTo = new Integer[2*N][2*N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 2*N; j++) compute(i, j);
			}
			trans = new long[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					trans[i][j] = fromTo[i][j+N];
					//System.out.println("trans[" + i + "][" + j + "] = " + trans[i][j]);
				}
			}
			long[][] ar = pow(T-1);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					max = Math.max(max, ar[i][j]);
				}
			}
			//System.out.println("LAST: " + Arrays.toString(cur));
			System.out.println(max);
		//}
	}

	static long[][] pow(int x) {
		if (x == 0) {
			long[][] retval = new long[trans.length][trans.length];
			for (int i = 0; i < trans.length; i++) retval[i][i] = 1;
			return retval;
		}
		else if (x == 1) return trans;
		else if (x % 2 == 0) {
			long[][] pow = pow(x/2);
			long[][] pow2 = pow;
			long[][] res = new long[trans.length][trans.length];
			for (int i = 0; i < trans.length; i++) {
				for (int j = 0; j < trans.length; j++) {
					for (int k = 0; k < trans.length; k++) {
						if (arr3[i] <= arr3[j] && arr3[j] <= arr3[k])
						res[i][k] = Math.max(res[i][k], pow[i][j]+pow2[j][k]-1);
					}
				}
			}
			return res;
		} else {
			long[][] pow = pow(x-1);
			long[][] pow2 = trans;
			long[][] res = new long[trans.length][trans.length];
			for (int i = 0; i < trans.length; i++) {
				for (int j = 0; j < trans.length; j++) {
					for (int k = 0; k < trans.length; k++) {
						if (arr3[i] <= arr3[j] && arr3[j] <= arr3[k])
						res[i][k] = Math.max(res[i][k], pow[i][j]+pow2[j][k]-1);
					}
				}
			}
			return res;
		}
	}

	static long[][] trans;

	static Integer[][] fromTo;

	static int compute(int x, int y) {
		if (fromTo[x][y] != null) return fromTo[x][y];
		if (arr3[x] > arr3[y]) return fromTo[x][y] = 0;
		int best = x <= y ? 1 : 0;
		for (int k = x+1; k <= y; k++) {
			if (arr3[x] <= arr3[k] && arr3[k] <= arr3[y]) {
				int val = 1+compute(k, y);
				best = Math.max(best, val);
			}
		}
		return fromTo[x][y] = best;
	}
}