#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
const long long inf = 1LL << 50;
template <typename T>
using m = map<T, int>;
using mt = long long[N][N];
mt d, dt;
int n;
long long T;
int a[N];
void one(mt a) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) a[i][j] = 0;
}
void copy(const mt a, mt b) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) b[i][j] = a[i][j];
}
void mul(const mt a, const mt b, mt c) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      c[i][j] = -inf;
      for (int k = 0; k < n; ++k) c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
    }
}
mt t, r;
void pow(const mt a, long long b, mt c) {
  copy(a, t);
  one(c);
  while (b) {
    if (b & 1) {
      mul(c, t, r);
      copy(r, c);
    }
    mul(t, t, r);
    copy(r, t);
    b >>= 1;
  }
}
int main() {
  scanf("%d%lld", &n, &T);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  for (int s = 0; s < n; s++) {
    for (int i = 0; i < n; i++) {
      if (a[i] < a[s]) {
        d[s][i] = -inf;
      } else {
        d[s][i] = 1;
        for (int j = 0; j < i; j++) {
          if (a[j] <= a[i]) {
            d[s][i] = max(d[s][i], d[s][j] + 1);
          }
        }
      }
    }
  }
  pow(d, T, dt);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans = max(ans, dt[i][j]);
    }
  }
  printf("%lld\n", ans);
}

### Prompt

Please formulate a CPP solution to the following problem:

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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
const long long inf = 1LL << 50;
template <typename T>
using m = map<T, int>;
using mt = long long[N][N];
mt d, dt;
int n;
long long T;
int a[N];
void one(mt a) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) a[i][j] = 0;
}
void copy(const mt a, mt b) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) b[i][j] = a[i][j];
}
void mul(const mt a, const mt b, mt c) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      c[i][j] = -inf;
      for (int k = 0; k < n; ++k) c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
    }
}
mt t, r;
void pow(const mt a, long long b, mt c) {
  copy(a, t);
  one(c);
  while (b) {
    if (b & 1) {
      mul(c, t, r);
      copy(r, c);
    }
    mul(t, t, r);
    copy(r, t);
    b >>= 1;
  }
}
int main() {
  scanf("%d%lld", &n, &T);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  for (int s = 0; s < n; s++) {
    for (int i = 0; i < n; i++) {
      if (a[i] < a[s]) {
        d[s][i] = -inf;
      } else {
        d[s][i] = 1;
        for (int j = 0; j < i; j++) {
          if (a[j] <= a[i]) {
            d[s][i] = max(d[s][i], d[s][j] + 1);
          }
        }
      }
    }
  }
  pow(d, T, dt);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans = max(ans, dt[i][j]);
    }
  }
  printf("%lld\n", ans);
}

```