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;

public class Main {

    public void solve() {
	Scanner scanner = new Scanner(System.in);
	int N = scanner.nextInt();
	int T = scanner.nextInt();
	int[] data = new int[N];
	int[] count = new int[301];
	for (int i = 0; i < N; i++) {
	    data[i] = scanner.nextInt();
	    count[data[i]]++;
	}
	scanner.close();

	int[] dp = new int[301];

	int sol = 0;
	int prevSol = 0;
	int increment = 0;
	for (int i = 0; i < Math.min(T, 300); i++) {
	    for (int j = 0; j < N; j++) {
		for (int k = data[j]; k >= 0; k--) {
		    dp[data[j]] = Math.max(dp[data[j]], dp[k] + 1);
		}
		sol = Math.max(sol, dp[data[j]]);
	    }
	    increment = sol - prevSol;
	    prevSol = sol;
	}

	sol += increment * Math.max(0, T - 300);

	System.out.println(sol);
    }

    public static void main(String[] args) {
	new Main().solve();
    }
}
