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 a[100001], b[100001], c, d, e, f;
int main() {
  scanf("%d%d", &c, &d);
  for (int g = 1, h[1001] = {0}; g <= c; g++) {
    scanf("%d", &a[g]);
    e = max(e, ++h[a[g]]);
  }
  for (int g = c + 1; g <= c * min(c, d); g++) a[g] = a[g - c];
  for (int g = 1; g <= c * min(c, d); g++) {
    b[g] = 1;
    for (int h = g - 1; h >= max(1, g - c); h--)
      if (a[g] >= a[h]) b[g] = max(b[g], b[h] + 1);
    f = max(f, b[g]);
  }
  if (c >= d)
    printf("%d", f);
  else
    printf("%d", f + e * (d - c));
  return 0;
}
