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.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class dupdated {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        FastReader in = new FastReader(inputStream);
        int n = in.nextInt();
        int t = in.nextInt();
        int temp = n*Math.min(t, n);
        int[] sequence = new int[n];
        int[] cost = new int[temp];
        int mox0 = 0;
        for (int i = 0; i < n; i++) {
            sequence[i] = in.nextInt();
            if (sequence[i] > mox0)
                mox0 = sequence[i];
        }
        int result = 0;
        for (int i = 0; i < temp; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (sequence[i % n] >= sequence[j % n] && cost[j] >= max)
                    max = cost[j];
            }
            cost[i] = max + 1;
            result = Math.max(result, cost[i]);
        }
        int[] frequency = new int[mox0];
        for (int i = 0; i < n; i++) {
            frequency[sequence[i]-1]++;
        }
        int localmax = 0;
        for (int i = 0; i < mox0; i++) {
            if (frequency[i] > localmax) {
                localmax = frequency[i];
            }
        }
        System.out.println(result + localmax * Math.max(0, t-n));
    }
}

class FastReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream) {
        this.stream = stream;
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public String next() {
        return readString();
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }

    public Long readLong() {
        return Long.parseLong(readString());
    }

    public Double readDouble() {
        return Double.parseDouble(readString());
        
}
}