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;
int n, s, T, ans;
int ar[101];
bool ok[301];
int dp[301][301];
int res[301][301];
int tmp[301][301];
int ways[24][301][301];
vector<int> v;
int main() {
  scanf("%d%d", &n, &T);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &ar[i]);
    ok[ar[i]] = true;
  }
  for (int i = 1; i < 301; i++)
    if (ok[i]) v.push_back(i);
  s = v.size();
  for (int h = 0; h < s; h++) {
    int head = v[h];
    dp[head][head] = 1;
    for (int i = 1; i <= n; i++) {
      int mx = dp[head][ar[i]];
      for (int j = 1; j <= ar[i]; j++)
        if (dp[head][j]) mx = max(mx, dp[head][j] + 1);
      dp[head][ar[i]] = mx;
    }
  }
  for (int i = 1; i < 301; i++)
    for (int j = 1; j < 301; j++) ways[0][i][j] = max(dp[i][j] - 1, 0);
  for (int kd = 1; (1 << kd) <= T; kd++)
    for (int i = 0; i < s; i++)
      for (int j = i; j < s; j++)
        for (int k = i; k <= j; k++) {
          int vi = v[i];
          int vj = v[j];
          int vk = v[k];
          ways[kd][vi][vj] = max(ways[kd][vi][vj],
                                 ways[kd - 1][vi][vk] + ways[kd - 1][vk][vj]);
        }
  for (int kd = 0; (1 << kd) <= T; kd++)
    if (T & (1 << kd)) {
      memset(tmp, 0, sizeof(tmp));
      for (int i = 0; i < s; i++)
        for (int j = i; j < s; j++)
          for (int k = i; k <= j; k++) {
            int vi = v[i];
            int vj = v[j];
            int vk = v[k];
            tmp[vi][vj] = max(tmp[vi][vj], res[vi][vk] + ways[kd][vk][vj]);
          }
      for (int i = 0; i < s; i++)
        for (int j = 0; j < s; j++) res[v[i]][v[j]] = tmp[v[i]][v[j]];
    }
  for (int i = 0; i < s; i++)
    for (int j = 0; j < s; j++) ans = max(ans, res[v[i]][v[j]]);
  printf("%d\n", ans);
  return 0;
}
