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;
import java.util.TreeMap;

public class TaskD {

	public static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		int n = in.nextInt();
		int t = in.nextInt();
		int[] a = new int[n];
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
			if (!map.containsKey(a[i])) {
				map.put(a[i], 1);
			} else {
				map.put(a[i], map.get(a[i]) + 1);
			}
		}

		int frequency = 0;
		for (int value: map.values()) {
			if (value > frequency) {
				frequency = value;
			}
		}

		int[][] dp = new int[n][n];
		dp[0][0] = 1;
		for (int j = 1; j < n; j++) {
			dp[0][j] = 1;
			for (int k = 0; k < j; k++) {
				if (a[k] <= a[j] && dp[0][k] + 1 > dp[0][j]) {
					dp[0][j] = dp[0][k] + 1;
				}
			}
			//System.out.print(dp[0][j] + " ");
		}
		//System.out.println();

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = dp[i - 1][j] + map.get(a[j]);
				for (int k = 0; k < n; k++) {
					if (k == j) continue;
					if (a[k] <= a[j]) {
						if (k < j && dp[i][k] + 1 > dp[i][j]) dp[i][j] = dp[i][k] + 1;
						if (k > j && dp[i - 1][k] + 1 > dp[i][j]) dp[i][j] = dp[i - 1][k] + 1;
					}
				}
				//System.out.print(dp[i][j] + " ");
			}
			//System.out.println();
		}

		int line = Math.min(t, n) - 1;
		int maximum = dp[line][0];
		for (int j = 1; j < n; j++) {
			maximum = Math.max(maximum, dp[line][j]);
		}
		if (t > n) {
			maximum += (t - n) * frequency;
		}
		System.out.println(maximum);
	}

}