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;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int t = min(m, 100);
  vector<int> b(n * t);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < t; j++) {
      b[n * j + i] = a[i];
    }
  }
  long long ans = 0;
  vector<int> d;
  int nn = b.size();
  for (int i = 0; i < nn; i++) {
    auto it = upper_bound(d.begin(), d.end(), b[i]);
    if (it == d.end()) {
      d.push_back(b[i]);
    } else {
      *it = b[i];
    }
  }
  ans = (long long)d.size();
  if (m > 100) {
    m -= 100;
    long long lm = (long long)m;
    map<int, long long> cnt;
    for (int i = 0; i < n; i++) {
      cnt[a[i]] += 1LL;
    }
    long long mm = 0;
    for (auto &p : cnt) {
      if (p.second > mm) {
        mm = p.second;
      }
    }
    ans += mm * m;
  }
  cout << ans << '\n';
  return 0;
}
