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 oo = 1e9;
int n, p, a[110];
struct matrix {
  int col, row, m[110][110];
  inline matrix operator*(const matrix &a) const {
    matrix b;
    b.col = b.row = n;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        b.m[i][j] = -oo;
        for (int k = 1; k <= n; ++k)
          b.m[i][j] = max(b.m[i][j], m[i][k] + a.m[k][j]);
      }
    return b;
  }
} mt, base, ans;
matrix Pow(matrix a, long long p) {
  matrix b = a, ans = a;
  --p;
  while (p > 0) {
    if (p % 2) ans = ans * b;
    b = b * b;
    p /= 2;
  }
  return ans;
}
void Build() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      mt.m[i][j] = base.m[i][j] = -oo;
      if (a[i] <= a[j]) base.m[i][j] = 1;
    }
  for (int i = 1; i <= n; ++i) {
    mt.m[i][i] = 0;
    for (int j = i + 1; j <= n; ++j)
      for (int k = i; k < j; ++k)
        if (a[j] >= a[k] && a[k] >= a[i])
          mt.m[i][j] = max(mt.m[i][j], mt.m[i][k] + 1);
  }
}
int main() {
  scanf("%d%d", &n, &p);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    ans.m[1][i] = 1;
  }
  Build();
  ans = ans * mt;
  if (p > 1) ans = ans * Pow(base * mt, p - 1);
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) res = max(res, ans.m[i][j]);
  }
  printf("%d", res);
}
