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<unsigned int> vc;
unsigned long long n, T;
void LIS(unsigned int ll, unsigned int hh, unsigned long long &len,
         unsigned long long &offset) {
  vector<unsigned int> dp_nn;
  vector<unsigned int> dp_nn_plus_n;
  dp_nn.resize(ll);
  dp_nn_plus_n.resize(hh);
  for (unsigned int i = 0; i < hh; ++i) dp_nn_plus_n[i] = 1;
  for (unsigned int i = 0; i < ll; ++i) dp_nn[i] = 1;
  for (unsigned int i = 0; i < hh; ++i) {
    for (unsigned int j = 0; j < i; ++j) {
      if (vc[i % n] >= vc[j % n]) {
        dp_nn_plus_n[i] = max(dp_nn_plus_n[i], dp_nn_plus_n[j] + 1);
        if (i < ll) dp_nn[i] = max(dp_nn[i], dp_nn[j] + 1);
      }
    }
  }
  sort(dp_nn_plus_n.begin(), dp_nn_plus_n.end());
  sort(dp_nn.begin(), dp_nn.end());
  unsigned long long h = dp_nn_plus_n[dp_nn_plus_n.size() - 1];
  unsigned long long l = dp_nn[dp_nn.size() - 1];
  offset = h - l;
  len = l;
  return;
}
int main() {
  cin >> n >> T;
  for (unsigned long long i = 0; i < n; ++i) {
    unsigned int x;
    cin >> x;
    vc.push_back(x);
  }
  unsigned long long mx = max(n, T);
  unsigned long long mn = min(n, T);
  unsigned long long lim = mn * n + n;
  unsigned long long delta = 0;
  unsigned long long L = 0;
  LIS(mn * n, lim, L, delta);
  unsigned long long pad = (mx - n) * delta;
  cout << L + pad << endl;
}
