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 main() {
  int n, t;
  cin >> n >> t;
  if (t <= 203) {
    int dp[n * t + 1][301];
    memset(dp, 0, sizeof(dp));
    int ar[n * t];
    int N = n * t;
    for (int ctr1 = 0; ctr1 < N; ctr1++) {
      if (ctr1 < n)
        cin >> ar[ctr1];
      else
        ar[ctr1] = ar[ctr1 - n];
    }
    for (int ctr1 = 1; ctr1 <= N; ctr1++) {
      for (int ctr2 = 0; ctr2 <= ar[ctr1 - 1]; ctr2++) {
        dp[ctr1][ar[ctr1 - 1]] =
            max(dp[ctr1][ar[ctr1 - 1]], 1 + dp[ctr1 - 1][ctr2]);
      }
      for (int ctr2 = 0; ctr2 <= 300; ctr2++)
        dp[ctr1][ctr2] = max(dp[ctr1][ctr2], dp[ctr1 - 1][ctr2]);
    }
    int r = 0;
    for (int ctr1 = 0; ctr1 <= 300; ctr1++) r = max(r, dp[N][ctr1]);
    cout << r << endl;
    return 0;
  } else {
    int dp[n * 101 + 1][301];
    memset(dp, 0, sizeof(dp));
    int ar[n * 101];
    int N = n * 101;
    int poj[301];
    memset(poj, 0, sizeof(poj));
    for (int ctr1 = 0; ctr1 < N; ctr1++) {
      if (ctr1 < n) {
        cin >> ar[ctr1];
        poj[ar[ctr1]]++;
      } else
        ar[ctr1] = ar[ctr1 - n];
    }
    for (int ctr1 = 1; ctr1 <= N; ctr1++) {
      for (int ctr2 = 0; ctr2 <= ar[ctr1 - 1]; ctr2++) {
        dp[ctr1][ar[ctr1 - 1]] =
            max(dp[ctr1][ar[ctr1 - 1]], 1 + dp[ctr1 - 1][ctr2]);
      }
      for (int ctr2 = 0; ctr2 <= 300; ctr2++)
        dp[ctr1][ctr2] = max(dp[ctr1][ctr2], dp[ctr1 - 1][ctr2]);
    }
    int dp2[n * 101 + 1][301];
    memset(dp2, 0, sizeof(dp2));
    for (int ctr1 = N - 1; ctr1 >= 0; ctr1--) {
      for (int ctr2 = 300; ctr2 >= ar[ctr1]; ctr2--) {
        dp2[ctr1][ar[ctr1]] = max(dp2[ctr1][ar[ctr1]], 1 + dp2[ctr1 + 1][ctr2]);
      }
      for (int ctr2 = 1; ctr2 <= 300; ctr2++)
        dp2[ctr1][ctr2] = max(dp2[ctr1][ctr2], dp2[ctr1 + 1][ctr2]);
    }
    int r = 0;
    int nt = t - 202;
    for (int ctr1 = 1; ctr1 <= 300; ctr1++)
      r = max(r, dp[N][ctr1] + dp2[0][ctr1] + nt * poj[ctr1]);
    cout << r << endl;
  }
  return 0;
}
