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, m;
int a[5000];
int gg[5000], g[200][200], ng[200][200];
int f[30][200][200];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
      if (a[j] >= a[i]) {
        gg[j] = 1;
        for (int k = 1; k <= j - 1; k++)
          if (a[k] >= a[i] && a[k] <= a[j]) gg[j] = max(gg[j], gg[k] + 1);
      } else
        gg[j] = 0;
    for (int j = 1; j <= n; j++) f[0][i][j] = gg[j];
  }
  for (int k = 1; k <= 25; k++) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        for (int t = 1; t <= n; t++)
          if (f[k - 1][i][j] != 0 && f[k - 1][j][t] != 0)
            f[k][i][t] = max(f[k][i][t], f[k - 1][i][j] + f[k - 1][j][t]);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) g[i][j] = f[0][i][j];
  int frst = 0;
  for (int k = 25; k >= 0; k--) {
    if ((m & (1 << k)) != 0) {
      if (frst == 0) {
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) g[i][j] = f[k][i][j];
        frst = 1;
      } else {
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) ng[i][j] = 0;
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
            for (int t = 1; t <= n; t++)
              if (g[i][j] != 0 && f[k][j][t] != 0)
                ng[i][t] = max(ng[i][t], g[i][j] + f[k][j][t]);
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) g[i][j] = ng[i][j];
      }
    }
  }
  int mx = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (g[i][j] > mx) mx = g[i][j];
  cout << mx << "\n";
  return 0;
}
