#include <bits/stdc++.h>
using namespace std;
int r;
int h;
int a[100];
int mat[100][100];
int ans[100][100];
int dp[100][100];
int dp2[100][100];
int m[100][100];
int tmp[100][100];
vector<int> xs;
void pow(int (&base)[100][100], int exp) {
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < r; j++) {
      ans[i][j] = 0;
      m[i][j] = base[i][j];
    }
  }
  while (exp > 0) {
    if (exp % 2 == 1) {
      for (int i = 0; i < r; i++) {
        for (int j = i; j < r; j++) {
          int t = 0;
          for (int k = i; k <= j; k++) {
            t = max(t, ans[i][k] + m[k][j]);
          }
          tmp[i][j] = t;
        }
      }
      for (int i = 0; i < r; i++) {
        for (int j = 0; j < r; j++) {
          ans[i][j] = tmp[i][j];
        }
      }
    }
    for (int i = 0; i < r; i++) {
      for (int j = i; j < r; j++) {
        int t = 0;
        for (int k = i; k <= j; k++) {
          t = max(t, m[i][k] + m[k][j]);
        }
        tmp[i][j] = t;
      }
    }
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        m[i][j] = tmp[i][j];
      }
    }
    exp /= 2;
  }
}
int main() {
  scanf("%d%d", &r, &h);
  for (int i = 0; i < r; i++) {
    scanf("%d", &a[i]);
    xs.push_back(a[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < r; i++) {
    int idx = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    for (int j = 0; j <= idx; j++) {
      for (int k = j; k <= idx; k++) {
        dp2[j][idx] = max(dp2[j][idx], dp[j][k] + 1);
      }
    }
    for (int j = 0; j < xs.size(); j++) {
      for (int k = 0; k < xs.size(); k++) {
        dp[j][k] = dp2[j][k];
      }
    }
  }
  r = xs.size();
  for (int i = r - 1; i >= 0; i--) {
    for (int j = 0; j < r; j++) {
      if (j >= 1) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
      if (i + 1 < r) dp[i][j] = max(dp[i][j], dp[i + 1][j]);
    }
  }
  pow(dp, h);
  printf("%d\n", ans[0][r - 1]);
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
int r;
int h;
int a[100];
int mat[100][100];
int ans[100][100];
int dp[100][100];
int dp2[100][100];
int m[100][100];
int tmp[100][100];
vector<int> xs;
void pow(int (&base)[100][100], int exp) {
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < r; j++) {
      ans[i][j] = 0;
      m[i][j] = base[i][j];
    }
  }
  while (exp > 0) {
    if (exp % 2 == 1) {
      for (int i = 0; i < r; i++) {
        for (int j = i; j < r; j++) {
          int t = 0;
          for (int k = i; k <= j; k++) {
            t = max(t, ans[i][k] + m[k][j]);
          }
          tmp[i][j] = t;
        }
      }
      for (int i = 0; i < r; i++) {
        for (int j = 0; j < r; j++) {
          ans[i][j] = tmp[i][j];
        }
      }
    }
    for (int i = 0; i < r; i++) {
      for (int j = i; j < r; j++) {
        int t = 0;
        for (int k = i; k <= j; k++) {
          t = max(t, m[i][k] + m[k][j]);
        }
        tmp[i][j] = t;
      }
    }
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        m[i][j] = tmp[i][j];
      }
    }
    exp /= 2;
  }
}
int main() {
  scanf("%d%d", &r, &h);
  for (int i = 0; i < r; i++) {
    scanf("%d", &a[i]);
    xs.push_back(a[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < r; i++) {
    int idx = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    for (int j = 0; j <= idx; j++) {
      for (int k = j; k <= idx; k++) {
        dp2[j][idx] = max(dp2[j][idx], dp[j][k] + 1);
      }
    }
    for (int j = 0; j < xs.size(); j++) {
      for (int k = 0; k < xs.size(); k++) {
        dp[j][k] = dp2[j][k];
      }
    }
  }
  r = xs.size();
  for (int i = r - 1; i >= 0; i--) {
    for (int j = 0; j < r; j++) {
      if (j >= 1) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
      if (i + 1 < r) dp[i][j] = max(dp[i][j], dp[i + 1][j]);
    }
  }
  pow(dp, h);
  printf("%d\n", ans[0][r - 1]);
}

```