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 f[500500], ans;
int mn, t, n;
int s[500500], a[500500];
unsigned long long read() {
  unsigned long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int main() {
  n = read();
  t = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  unsigned long long now = 0, tmp;
  for (int i = 1; i <= min(2 * n, t); i++) {
    tmp = now;
    for (int j = 1; j <= n; j++) {
      unsigned long long x = now;
      while (f[x] > a[j]) x--;
      if (x == now) f[++now] = int(1e9);
      f[x + 1] = min(f[x + 1], a[j]);
    }
  }
  if (t <= 2 * n)
    printf("%lld\n", now);
  else
    printf("%lld\n", now + (now - tmp) * (t - 2 * n));
  return 0;
}
