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


if __name__ == '__main__':
    n, t = map(int, raw_input().split())
    a = map(int, raw_input().split())
    r = a * min(n, t)
    d = [min(a) - 1]
    for i in r:
        p = bisect.bisect_right(d, i)
        if p < len(d):
            d[p] = i
        else:
            d.append(i)
    l = len(d) - 1
    if t < n:
        print l
    else:
        counts = Counter(a)
        print l + (t - n) * max(counts.itervalues())


