No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Once Again...

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an array of positive integers *a*_{1}, *a*_{2}, ..., *a*_{n × T} of length *n* × *T*. We know that for any *i* > *n* it is true that *a*_{i} = *a*_{i - 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* ≤ 10^{7}). The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/09/2021 10:55:33 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|