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;
const int MAXN = 110;
int n, seg[MAXN], t, m = 0, dp[MAXN][MAXN][MAXN], mat[MAXN][MAXN],
                     tmp[MAXN][MAXN], ans[MAXN][MAXN];
map<int, int> mp;
inline void compress() {
  set<int> tmp;
  for (int i = 0; i < n; i++) tmp.insert(seg[i]);
  while (!tmp.empty()) {
    mp[*tmp.begin()] = m;
    m++;
    tmp.erase(*tmp.begin());
  }
  for (int i = 0; i < n; i++) seg[i] = mp[seg[i]];
  return;
}
inline void mul(int a[MAXN][MAXN], int b[MAXN][MAXN], int res[MAXN][MAXN]) {
  for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++) {
      res[i][j] = 0ll;
      for (int k = i; k <= j; k++)
        res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
    }
  return;
}
inline void pw(int a[MAXN][MAXN], int b, int res[MAXN][MAXN]) {
  for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++) res[i][j] = 0;
  while (b) {
    if (b & 1) {
      mul(res, a, tmp);
      memcpy(res, tmp, sizeof tmp);
    }
    mul(a, a, tmp);
    memcpy(a, tmp, sizeof tmp);
    b /= 2ll;
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> t;
  for (int i = 0; i < n; i++) cin >> seg[i];
  compress();
  for (int k = 0; k < n; k++)
    for (int i = 0; i < m; i++)
      for (int j = i; j < m; j++) {
        dp[i][j][k + 1] = dp[i][j][k];
        if (seg[k] >= i && seg[k] <= j)
          dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][seg[k]][k] + 1);
      }
  for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++) mat[i][j] = dp[i][j][n];
  pw(mat, t, ans);
  cout << ans[0][m - 1] << endl;
  return 0;
}
