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. 
# -*- coding: utf-8 -*-
import sys,math,heapq,itertools as it,fractions,re,bisect,collections as coll

MX = 110
n, T = map(int, raw_input().split())
a = map(int, raw_input().split())
a = a * min(T, MX)
m = len(a)
nums = [1] * m
for i in xrange(m - 1, -1, -1):
    tmp = 0
    for j in xrange(i + 1, min(m, i + 1 + 2 * n)):
        if a[j] >= a[i]:
            tmp = max(tmp, nums[j])
    nums[i] += tmp

if T <= MX:
    print max(nums)
else:
    ans = 0
    for i in xrange(n):
        ans = max(ans, nums[i] + (nums[i] - nums[i + n]) * (T - MX))
    print ans
