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>> merge(const vector<vector<int>>& p,
                          const vector<vector<int>>& q) {
  const int n = p.size();
  vector<vector<int>> r(n, vector<int>(n));
  for (int i = 0; i < (int)(n); ++i) {
    for (int j = 0; j < (int)(n); ++j) {
      if (j < i) {
        continue;
      }
      for (int k = i; k <= j; ++k) {
        r[i][j] = max(r[i][j], p[i][k] + q[k][j]);
      }
    }
  }
  return r;
}
int lis(const vector<int>& xs) {
  const int n = xs.size();
  vector<int> dp(n + 1, 1 << 30);
  dp[0] = 0;
  int ans = 0;
  for (int x : xs) {
    int p = 0, q = n + 1;
    while (q - p > 1) {
      int m = (p + q) / 2;
      if (dp[m] > x) {
        q = m;
      } else {
        p = m;
      }
    }
    dp[p + 1] = min(dp[p + 1], x);
    ans = max(ans, p + 1);
  }
  return ans;
}
vector<vector<int>> pow(const vector<vector<int>>& mat, int n) {
  if (n == 1) {
    return mat;
  }
  vector<vector<int>> sq = pow(mat, n / 2);
  sq = merge(sq, sq);
  if (n & 1) {
    return merge(sq, mat);
  } else {
    return sq;
  }
}
int main() {
  int n, t;
  cin >> n >> t;
  vector<int> xs(n);
  for (int i = 0; i < (int)(n); ++i) {
    cin >> xs[i];
  }
  set<int> xset(xs.begin(), xs.end());
  map<int, int> comp;
  for (auto x : xset) {
    const int i = comp.size();
    comp[x] = i;
  }
  for (int i = 0; i < (int)(n); ++i) {
    xs[i] = comp[xs[i]];
  }
  vector<vector<int>> one(n, vector<int>(n));
  for (int i = 0; i < (int)(n); ++i) {
    for (int j = i; j < n; ++j) {
      vector<int> pxs;
      for (auto x : xs) {
        if (i <= x && x <= j) {
          pxs.push_back(x);
        }
      }
      one[i][j] = lis(pxs);
    }
  }
  cout << pow(one, t)[0][n - 1] << endl;
  return 0;
}
