#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const int MAXA = 310;
int n, T;
int a[MAXN], l[MAXN][MAXN], r[MAXN][MAXN], cnt[MAXA];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> T;
  for (int i = (1), _b = (n); i <= _b; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  for (int k = (1), _b = (n + 1); k <= _b; k++)
    for (int i = (1), _b = (n); i <= _b; i++) {
      l[k][i] = 1;
      for (int j = (1), _b = (n); j <= _b; j++)
        if (a[j] <= a[i]) l[k][i] = max(l[k][i], l[k - 1][j] + 1);
      for (int j = (1), _b = (i - 1); j <= _b; j++)
        if (a[j] <= a[i]) l[k][i] = max(l[k][i], l[k][j] + 1);
    }
  for (int k = (1), _b = (n + 1); k <= _b; k++)
    for (int i = (n), _b = (1); i >= _b; i--) {
      r[k][i] = 1;
      for (int j = (n), _b = (1); j >= _b; j--)
        if (a[j] >= a[i]) r[k][i] = max(r[k][i], r[k - 1][j] + 1);
      for (int j = (n), _b = (i + 1); j >= _b; j--)
        if (a[j] >= a[i]) r[k][i] = max(r[k][i], r[k][j] + 1);
    }
  int res = 0;
  if (T == 1) {
    for (int i = (1), _b = (n); i <= _b; i++) res = max(res, l[T][i]);
  } else if (T <= n * 2) {
    for (int i = (1), _b = (n); i <= _b; i++)
      res = max(res, l[T / 2][i] + r[T - T / 2 + 1][i] - 1);
  } else {
    for (int i = (1), _b = (n); i <= _b; i++) {
      int cal = cnt[a[i]] * (T - 2 * n);
      for (int j = (n), _b = (1); j >= _b; j--)
        if (a[j] == a[i]) {
          cal += l[n][j];
          break;
        }
      for (int j = (1), _b = (n); j <= _b; j++)
        if (a[j] == a[i]) {
          cal += r[n][j];
          break;
        }
      res = max(res, cal);
    }
  }
  cout << res;
}

### Prompt

In cpp, your task is to solve 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 MAXN = 110;
const int MAXA = 310;
int n, T;
int a[MAXN], l[MAXN][MAXN], r[MAXN][MAXN], cnt[MAXA];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> T;
  for (int i = (1), _b = (n); i <= _b; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  for (int k = (1), _b = (n + 1); k <= _b; k++)
    for (int i = (1), _b = (n); i <= _b; i++) {
      l[k][i] = 1;
      for (int j = (1), _b = (n); j <= _b; j++)
        if (a[j] <= a[i]) l[k][i] = max(l[k][i], l[k - 1][j] + 1);
      for (int j = (1), _b = (i - 1); j <= _b; j++)
        if (a[j] <= a[i]) l[k][i] = max(l[k][i], l[k][j] + 1);
    }
  for (int k = (1), _b = (n + 1); k <= _b; k++)
    for (int i = (n), _b = (1); i >= _b; i--) {
      r[k][i] = 1;
      for (int j = (n), _b = (1); j >= _b; j--)
        if (a[j] >= a[i]) r[k][i] = max(r[k][i], r[k - 1][j] + 1);
      for (int j = (n), _b = (i + 1); j >= _b; j--)
        if (a[j] >= a[i]) r[k][i] = max(r[k][i], r[k][j] + 1);
    }
  int res = 0;
  if (T == 1) {
    for (int i = (1), _b = (n); i <= _b; i++) res = max(res, l[T][i]);
  } else if (T <= n * 2) {
    for (int i = (1), _b = (n); i <= _b; i++)
      res = max(res, l[T / 2][i] + r[T - T / 2 + 1][i] - 1);
  } else {
    for (int i = (1), _b = (n); i <= _b; i++) {
      int cal = cnt[a[i]] * (T - 2 * n);
      for (int j = (n), _b = (1); j >= _b; j--)
        if (a[j] == a[i]) {
          cal += l[n][j];
          break;
        }
      for (int j = (1), _b = (n); j <= _b; j++)
        if (a[j] == a[i]) {
          cal += r[n][j];
          break;
        }
      res = max(res, cal);
    }
  }
  cout << res;
}

```