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 a[112], dp[312][312], mnix[312];
int **func(int **mat1, int **mat2, int mx) {
  int **ans;
  ans = new int *[mx + 2];
  for (int i = 1; i <= mx; i++) {
    ans[i] = new int[mx + 2];
    for (int j = 1; j <= mx; j++) {
      ans[i][j] = 0;
      for (int k = i; k <= j; k++)
        ans[i][j] = max(ans[i][j], mat1[i][k] + mat2[k][j]);
    }
  }
  return ans;
}
int main() {
  int n, k, mx = 0;
  cin >> n >> k;
  for (int i = 0; i < 312; i++) {
    mnix[i] = 500;
    for (int j = 0; j < 312; j++) {
      dp[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    mx = max(mx, a[i]);
    mnix[a[i]] = min(mnix[a[i]], i);
  }
  int **mat;
  mat = new int *[312];
  for (int i = 0; i < 312; i++) {
    mat[i] = new int[312];
    for (int j = 0; j < 312; j++) mat[i][j] = 0;
  }
  for (int st = 1; st <= mx; st++) {
    if (mnix[st] > 200) continue;
    for (int j = 1; j <= mx; j++) {
      if (j >= st)
        dp[mnix[st]][j] = 1;
      else
        dp[mnix[st]][j] = 0;
    }
    for (int i = mnix[st] + 1; i < n; i++) {
      for (int j = 1; j <= mx; j++) {
        if (a[i] < st)
          dp[i][j] = dp[i - 1][j];
        else if (j < a[i])
          dp[i][j] = dp[i - 1][j];
        else if (j == a[i])
          dp[i][j] = dp[i - 1][j] + 1;
        else
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    for (int j = 1; j <= mx; j++) {
      if (j < st) mat[st][j] = 0;
      mat[st][j] = dp[n - 1][j];
    }
    for (int i = 0; i <= mx; i++) {
      for (int j = 0; j <= mx; j++) {
        dp[i][j] = 0;
      }
    }
  }
  int **ans;
  ans = new int *[mx + 2];
  for (int i = 0; i <= mx; i++) {
    ans[i] = new int[mx + 2];
    for (int j = 0; j <= mx; j++) ans[i][j] = 0;
  }
  while (k) {
    if (k % 2 == 1) ans = func(ans, mat, mx);
    mat = func(mat, mat, mx);
    k = k / 2;
  }
  int fans = 0;
  for (int j = 1; j <= mx; j++) fans = max(fans, ans[j][mx]);
  cout << fans << endl;
}
