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. 
import sys
from collections import Counter

#sys.stdin = open("input.txt")
#sys.stdout = open("output.txt", "w")

n, t = [int(i) for i in input().split()]
lst = [int(i) for i in input().split()]
cnt = Counter(lst)
mostlst = cnt.most_common()
freq = mostlst[0][1]

#print("freq = ", freq, sep='')

curlist = lst

curt = 1
d = [0 for i in range(n)]
prevmax = 0
curmax = 0
ans = 0
while curt <= t:
	d += [1 for i in range(n)]
	#print(d)
	ind = curt * n
	#print("from =", ind - n)
	for i in range(n):
		for j in range(-n, i):
			if lst[j] <= lst[i]:
				d[ind + i] = max(d[ind + i], d[ind + j] + 1)
	curmax = max(d[ind:ind + n])
	if curmax - prevmax == freq:
		ans = curmax + freq * (t - curt)
		break
	curt += 1
	prevmax = curmax
else:
	ans = curmax

#print(d)
#print(curt)
print(ans)