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 = 1e2 + 10, MAXT = 1e7 + 10;
const long long int Inf = 1e9 + 10;
long long int n, T, a[MAXN], ans;
vector<vector<long long int>> mul(vector<vector<long long int>> a,
                                  vector<vector<long long int>> b) {
  int n1 = a.size(), m1 = a[0].size();
  int n2 = b.size(), m2 = b[0].size();
  vector<vector<long long int>> c(n1);
  for (int i = 0; i < n1; i++) {
    c[i].resize(m2);
    for (int j = 0; j < m2; j++) {
      long long int x = -Inf;
      for (int k = 0; k < n2; k++) {
        x = max(x, a[i][k] + b[k][j] - 1);
      }
      c[i][j] = x;
    }
  }
  return c;
}
vector<vector<long long int>> pw(vector<vector<long long int>> a, int b) {
  if (b == 1) return a;
  vector<vector<long long int>> p = pw(a, b >> 1);
  p = mul(p, p);
  if (b & 1) p = mul(p, a);
  return p;
}
int findAns(int l, int r) {
  int dp[n];
  fill(dp, dp + n, -Inf);
  dp[l] = 1;
  for (int i = l + 1; i < n; i++) {
    if (a[i] >= a[l]) {
      for (int j = l; j < i; j++) {
        if (a[i] >= a[j]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
  }
  int dp2[n];
  fill(dp2, dp2 + n, -Inf);
  for (int i = 0; i <= r; i++) {
    if (a[i] >= a[l]) {
      for (int j = 0; j < i; j++) {
        if (a[i] >= a[j]) {
          dp2[i] = max(dp2[i], dp2[j] + 1);
        }
      }
      for (int j = l; j < n; j++) {
        if (a[i] >= a[j]) {
          dp2[i] = max(dp2[i], dp[j] + 1);
        }
      }
    }
  }
  return dp2[r];
}
vector<vector<long long int>> makeT() {
  vector<vector<long long int>> a(n);
  for (int i = 0; i < n; i++) a[i].resize(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      a[i][j] = findAns(i, j);
    }
  }
  return a;
}
void log(vector<vector<long long int>> m) {
  for (auto row : m) {
    for (int x : row) cerr << x << " ";
    cerr << endl;
  }
}
int main() {
  cin >> n >> T;
  for (int i = 0; i < n; i++) cin >> a[i];
  if (T > 1) {
    vector<vector<long long int>> x = pw(makeT(), T - 1);
    for (int i = 0; i < n; i++) {
      ans = max(ans, *max_element(x[i].begin(), x[i].end()));
    }
  } else {
    int dp[n];
    for (int i = 0; i < n; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++)
        if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1);
      ans = max(ans, (long long int)dp[i]);
    }
  }
  cout << ans;
}
