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 TaskD {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int T = scanner.nextInt();
        int t = T;
        if (t > 210) {
            t = 210;
        }
        int a[] = new int[n * t];
        for (int i = 0; i < n; i += 1) {
            a[i] = scanner.nextInt();
        }
        for (int i = n; i < n * t; i += 1) {
            a[i] = a[i-n];
        }
        int f[] = new int[n * t];
        int p[] = new int[n * t];
        for (int i = 0; i < n * t; i += 1) {
            f[i] = 1;
            for (int j = 0; j < i; j += 1) {
                if (a[j] <= a[i] && f[j] + 1 > f[i]) {
                    f[i] = f[j] + 1;
                    p[i] = j;
                }
            }
        }
        int result;
        if (T > t) {
            int pt = 105;
            int cnt = 0;
            int pos = n * t - 1;
            for (int i = n * (t - 1); i < n * t; i += 1) {
                if (f[i] > f[pos]) {
                    pos = i;
                }
            }
            while (pos >= n * pt) {
                pos = p[pos];
            }
            while (pos >= n * (pt - 1)) {
                pos = p[pos];
                cnt++;
            }

            /* int r[] = new int[20];
            int dp = pos;
            for (int i = 0; i < 20; i += 1) {
                r[i] = a[dp];
                dp = p[dp];
            }
            for (int i = 19; i >= 0; i--) {
                System.out.print(r[i] + " ");
            }
            System.out.println();
*/
            int lpos = n * t - 1;
            for (int i = n * (t - 1); i < n * t; i += 1) {
                if (f[i] > f[lpos]) {
                    lpos = i;
                }
            }
            result = f[lpos] + (T - t) * cnt;
        } else {
            int max = f[0];
            for (int i = 0; i < n * t; i += 1) {
                max = Math.max(max, f[i]);
            }
            result = max;
        }
        System.out.println(result);
    }
}
