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. 
def solve():
    n,T = map(int,input().split())
    array = list(map(int,input().split()))
    ElementsTillN = {}
    for x in range(n):
        ElementsTillN[x]={array[x]:1}
    for x in range(1,n):
        for y in range(x):
            if array[y]<=array[x]:
                for value,num in ElementsTillN[y].items():
                    if value in ElementsTillN[x]:
                        ElementsTillN[x][value]=max(num+1,ElementsTillN[x][value])
                    else:
                        ElementsTillN[x][value]=num+1
    newElementsTillN = {}
    for x in range(n):
        valueAtIndex = array[x]
        if valueAtIndex  not in newElementsTillN:
            newElementsTillN[valueAtIndex]={}
        for value,num in ElementsTillN[x].items():
            if value in newElementsTillN[valueAtIndex]:
                newElementsTillN[valueAtIndex][value]=max(num,newElementsTillN[valueAtIndex][value])
            else:
                newElementsTillN[valueAtIndex][value]=num            
    # print (newElementsTillN)
    # print ("##################")
    valueSoFar = [0]*301
    changes = [0]*110
    for x in range(min(110,T)):
        currentSoFar = [0]*301
        for end in newElementsTillN.keys():
            for start in array:
                if start<=end:
                    for newStart,value in newElementsTillN[end].items():
                        if newStart>=start:
                            currentSoFar[end]= max(currentSoFar[end],value+valueSoFar[start])
        changes[x] = max(currentSoFar)-max(valueSoFar)
        # print (changes[x])
        valueSoFar = currentSoFar
        # for index in range(301):
        #     if valueSoFar[index]:
                # print (index,valueSoFar[index])
        # print ("#####################")
    T-=110
    # print (changes)
    if T>0:
        print (max(valueSoFar)+ T*changes[-1])
    else:
        print (max(valueSoFar))
solve()