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.*;
import java.util.*;
public class B582 {
public static void main(String[] args) throws IOException {
	input.init(System.in);
	PrintWriter out = new PrintWriter(System.out);
	int n = input.nextInt(), T = input.nextInt();
	int[] as = new int[n];
	for(int i = 0; i<n; i++) as[i] = input.nextInt();
	long[][] g = new long[2*n][2*n];
	for(int i = 0; i<2*n; i++)
		for(int j = i+1; j<2*n; j++)
			if(as[i%n] <= as[j%n]) g[i][j] = 1;
			else g[i][j] = -99999999;
	for(int k = 0; k<2*n; k++)
		for(int i = 0; i<k; i++)
			for(int j =k+1; j<2*n; j++)
				g[i][j] = Math.max(g[i][j], g[i][k] + g[k][j]);
	//for(long[] A : g) out.println(Arrays.toString(A));
	long[][] m = new long[n][n];
	for(int i = 0; i<n; i++)
		for(int j = 0; j<n; j++)
			m[i][j] = g[i][j+n];
	//for(long[] A : m) out.println(Arrays.toString(A));
	long[][] pow = mpow(m, T-1);
	//for(long[] A : pow) out.println(Arrays.toString(A));
	long res = 0;
	for(int i = 0; i<n; i++)
		for(int j = 0; j<n; j++)
			res = Math.max(res, pow[i][j]);
	if(T == 1) 
	{
		for(int i = 0; i<n; i++)
			for(int j = 0; j<n; j++)
				res = Math.max(res, m[i][j]);
	}
	out.println(res);
	out.close();
}
//return a^1 + a^2 + ... + a^k
//returns a^k
//O(log(k)*n^3)
public static long[][] mpow(long[][] a, long k)
{
  if (k == 0)
      return munit(a.length);
  else if (k % 2 == 0)
  {
      return mpow(mmul(a, a), k / 2);
  }
  else
  {
      return mmul(a, mpow(a, k - 1));
  }
}
//O(n^3)
public static long[][] mmul(long[][] a, long[][] b)
{
  long[][] c = new long[a.length][b[0].length];
  for (int i = 0; i < a.length; ++i)
      for (int j = 0; j < b[0].length; ++j)
      {
          long z = Math.max(a[i][j], b[i][j]);
          for (int k = 0; k < b.length; ++k)
          {
              z = Math.max(z, (a[i][k] + b[k][j]));
          }
          c[i][j] = z;
      }
  return c;

}
//O(n^2)
public static long[][] madd(long[][] a, long[][] b)
{
  long[][] c = new long[a.length][a[0].length];
  for (int i = 0; i < a.length; ++i)
      for (int j = 0; j < a[0].length; ++j)
      {
          c[i][j] = (a[i][j] + b[i][j]);
      }
  return c;
}
//O(n^2)
public static long[][] munit(int len)
{
  long[][] res = new long[len][len];
  for (int i = 0; i < len; ++i)
      res[i][i] = 1;
  return res;
}
public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}

