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. 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> matrixMultiply(const vector<vector<int>> &A,
                                   const vector<vector<int>> &B) {
  assert(A.size() == B.size());
  if (A.size() > 0) {
    assert(A.size() == A.back().size());
    assert(A.size() == B.back().size());
  }
  int N = A.size();
  vector<vector<int>> C(N, vector<int>(N, -1));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int k = 0; k < N; ++k) {
        if (A[i][k] >= 0 && B[k][j] >= 0) {
          C[i][j] = max(C[i][j], A[i][k] + B[k][j]);
        }
      }
    }
  }
  return C;
}
int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, T;
  cin >> N >> T;
  vector<int> A;
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    A.push_back(a);
  }
  vector<vector<int>> X(N, vector<int>(N, 0));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (A[j] >= A[i]) {
        X[i][j] = 1;
        for (int k = 0; k < j; ++k) {
          if (A[i] <= A[k] && A[k] <= A[j]) X[i][j] = max(X[i][j], X[i][k] + 1);
        }
      } else {
        X[i][j] = -1;
      }
    }
  }
  vector<vector<int>> Y(N, vector<int>(N, 0));
  while (T > 0) {
    if ((T & 1) == 1) {
      Y = matrixMultiply(Y, X);
    }
    T >>= 1;
    X = matrixMultiply(X, X);
  }
  int maxSequence = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      maxSequence = max(Y[i][j], maxSequence);
    }
  }
  cout << maxSequence << endl;
  return 0;
}
