#include <bits/stdc++.h>
using namespace std;
mt19937_64 random_num(
    chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1000000007;
const int base = 26;
const int arsz = 105;
int n, T;
vector<int> v;
int a[105], cnt[105];
int t[105];
int f[105][105];
int L[105][105], R[105][105];
int res;
void preprocess() {
  for (int i = 1; i <= n; i++) v.push_back(a[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    cnt[a[i]]++;
  }
}
void process() {
  for (int l = 1; l <= v.size(); l++)
    for (int r = l + 1; r <= v.size(); r++) {
      for (int i = 1; i <= n; i++) {
        t[i] = INT_MIN;
        if (a[i] >= l) t[i] = 1;
      }
      for (int i = 1; i <= n; i++)
        if (l <= a[i] && a[i] <= r)
          for (int j = 1; j <= i - 1; j++)
            if (l <= a[j] && a[j] <= a[i]) t[i] = max(t[i], t[j] + 1);
      for (int i = 1; i <= n; i++)
        if (l <= a[i] && a[i] <= r) f[l][r] = max(f[l][r], t[i]);
    }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> T;
  for (int i = 1; i <= n; i++) cin >> a[i];
  preprocess();
  process();
  for (int i = 1; i <= v.size(); i++) L[i][0] = R[i][0] = 0;
  for (int i = 0; i < v.size(); i++)
    for (int j = 1; j <= v.size(); j++)
      for (int k = j + 1; k <= v.size(); k++)
        L[i + 1][k] = max(L[i + 1][k], L[i][j] + f[j][k]);
  for (int i = 0; i < v.size(); i++)
    for (int j = 1; j <= v.size(); j++)
      for (int k = 1; k < j; k++)
        R[k][i + 1] = max(R[k][i + 1], R[j][i] + f[k][j]);
  res = T;
  for (int i = 1; i <= v.size(); i++)
    for (int j = 0; j <= v.size(); j++)
      for (int k = 0; k <= v.size(); k++)
        if (j + k <= T)
          res = max(res, L[j][i] + cnt[i] * (T - j - k) + R[i][k]);
  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;
mt19937_64 random_num(
    chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1000000007;
const int base = 26;
const int arsz = 105;
int n, T;
vector<int> v;
int a[105], cnt[105];
int t[105];
int f[105][105];
int L[105][105], R[105][105];
int res;
void preprocess() {
  for (int i = 1; i <= n; i++) v.push_back(a[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    cnt[a[i]]++;
  }
}
void process() {
  for (int l = 1; l <= v.size(); l++)
    for (int r = l + 1; r <= v.size(); r++) {
      for (int i = 1; i <= n; i++) {
        t[i] = INT_MIN;
        if (a[i] >= l) t[i] = 1;
      }
      for (int i = 1; i <= n; i++)
        if (l <= a[i] && a[i] <= r)
          for (int j = 1; j <= i - 1; j++)
            if (l <= a[j] && a[j] <= a[i]) t[i] = max(t[i], t[j] + 1);
      for (int i = 1; i <= n; i++)
        if (l <= a[i] && a[i] <= r) f[l][r] = max(f[l][r], t[i]);
    }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> T;
  for (int i = 1; i <= n; i++) cin >> a[i];
  preprocess();
  process();
  for (int i = 1; i <= v.size(); i++) L[i][0] = R[i][0] = 0;
  for (int i = 0; i < v.size(); i++)
    for (int j = 1; j <= v.size(); j++)
      for (int k = j + 1; k <= v.size(); k++)
        L[i + 1][k] = max(L[i + 1][k], L[i][j] + f[j][k]);
  for (int i = 0; i < v.size(); i++)
    for (int j = 1; j <= v.size(); j++)
      for (int k = 1; k < j; k++)
        R[k][i + 1] = max(R[k][i + 1], R[j][i] + f[k][j]);
  res = T;
  for (int i = 1; i <= v.size(); i++)
    for (int j = 0; j <= v.size(); j++)
      for (int k = 0; k <= v.size(); k++)
        if (j + k <= T)
          res = max(res, L[j][i] + cnt[i] * (T - j - k) + R[i][k]);
  cout << res;
}

```