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 N = 11004, MAX = 333;
int a[N], lis[N], cnt[MAX];
int main() {
  int n, t;
  scanf("%d %d", &n, &t);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    ++cnt[a[i]];
    for (int j = 0; j < n; ++j) a[i + j * n] = a[i];
  }
  int oldn = n;
  n = n * min(n + 1, t);
  vector<int> d;
  for (int i = 0; i < min(oldn + 1, t); ++i) {
    for (int j = 0; j < oldn; ++j) {
      auto it = upper_bound(d.begin(), d.end(), a[j]);
      if (it == d.end())
        d.push_back(a[j]);
      else
        *it = a[j];
    }
  }
  printf("%d\n",
         (int)d.size() + *max_element(cnt, cnt + MAX) * max(0, t - oldn - 1));
}
