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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class OnceAgain {

    static final int INF = (int) 1e5;

    int n;

    void solve() {
        n = in.nextInt();
        int T = in.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) A[i] = in.nextInt();

        // M[i][j] = the max length of sequence that start with element index ≥ i and end strictly with element at j
        int[][] M = new int[n][n];
        for (int s = 0; s < n; s++) {
            for (int i = 0; i < n; i++) {
                if (A[s] > A[i]) {
                    M[s][i] = -INF;
                } else {
                    M[s][i] = 1;
                    for (int j = 0; j < i; j++) {
                        if (A[j] <= A[i]) M[s][i] = Math.max(M[s][i], M[s][j] + 1);
                    }
                }
            }
        }

        // calc the max non-decreasing sub-sequences
        int[][] res = pow(M, T);

        // find the max element as the answer
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, res[i][j]);
            }
        }
        out.println(ans);
    }

    private int[][] pow(int[][] M, int T) {
        int[][] B = new int[n][n];
        while (T > 0) {
            if ((T & 1) > 0) B = mul(B, M);
            M = mul(M, M);
            T >>= 1;
        }
        return B;
    }

    private int[][] mul(int[][] A, int[][] B) {
        int[][] R = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                R[i][j] = -INF;
                for (int k = 0; k < n; k++) {
                    R[i][j] = Math.max(R[i][j], A[i][k] + B[k][j]);
                }
            }
        }
        return R;
    }

    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new OnceAgain().solve();
        out.close();
    }

    static FastScanner in;
    static PrintWriter out;

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner(BufferedReader in) {
            this.in = in;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
