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<long long int> > cache(10000001);
vector<long long int> as;
void walk(long long int N) {
  if (cache[N].size()) return;
  cache[N].resize(300 * 300, 0);
  if (N == 1) {
    for (long long int n = 0; n < as.size(); ++n) {
      for (long long int i = 0; i < 300; ++i) {
        for (long long int j = 299; j >= i; --j) {
          long long int idx = i + 300 * j;
          if (i <= as[n] && as[n] <= j)
            cache[1][idx] = max(cache[1][idx], 1 + cache[1][i + 300 * as[n]]);
        }
      }
    }
  } else {
    walk(N / 2);
    walk(N - N / 2);
    for (long long int i = 0; i < 300; ++i)
      for (long long int j = i; j < 300; ++j) {
        long long int idx = i + 300 * j;
        cache[N][idx] = 0;
        for (long long int k = i; k <= j; ++k)
          cache[N][idx] = max(cache[N][idx], cache[N / 2][i + 300 * k] +
                                                 cache[N - N / 2][k + 300 * j]);
      }
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  long long int N, T;
  cin >> N >> T;
  as.resize(N);
  for (long long int n = 0; n < N; ++n) {
    cin >> as[n];
    as[n]--;
  }
  walk(T);
  long long int res = 0;
  for (long long int i = 0; i < 300; ++i)
    for (long long int j = i; j < 300; ++j)
      res = max(res, cache[T][i + 300 * j]);
  cout << res << endl;
  return 0;
}
