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 n, t, T, a[105], maxi, mem[40010][105], rep[310], maxrep;
int sol(int i, int last) {
  if (i > n * t) return 0;
  int &ret = mem[i][last];
  if (ret != -1) return ret;
  ret = 0;
  int ii = (i % n);
  if (ii == 0) ii = n;
  if (a[ii] >= a[last]) ret = 1 + sol(i + 1, ii);
  ret = max(ret, sol(i + 1, last));
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  memset(mem, -1, sizeof(mem));
  cin >> n >> T;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    rep[a[i]]++;
    maxrep = max(maxrep, rep[a[i]]);
  }
  int add = 0;
  if (T > 410) {
    t = 400;
    T -= 400;
    add = maxrep * T;
  } else
    t = T;
  cout << sol(1, 0) + add;
  return 0;
}
