The Prime Minister of Bajtocja is traveling along the main highway of Bajtocja to visit one of the members of his party, and television is broadcasting the journey live. The Prime Minister starts with a full tank and would be able to complete the entire route without refueling. However, he decided to show on television how he refuels the car himself, believing it would help improve his image.

There is a gas station every bajtomile along the highway. Each station belongs to one of $m$ chains. The Prime Minister would like to refuel at as many stations as possible. His advisors suggested that if any two refuels among $k$ consecutive refuels take place at stations belonging to the same chain, it could be perceived as showing excessive favoritism toward that specific chain. The Prime Minister wants to avoid such a PR blunder at all costs.

You are given the chain numbers of the consecutive stations along the highway and the parameter $k$. Determine the length of the longest subsequence of stations that satisfies the advisors' condition.

Input

The first line of input contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 10\,000$, $2 \le k \le 5$), representing the number of stations, the number of chains, and the parameter specified by the advisors, respectively. The second line contains a sequence of $n$ integers $a_i$ ($1 \le a_i \le m$), where the $i$-th number denotes the chain number to which the $i$-th station belongs.

Output

The first and only line of output should contain a single positive integer $t$, representing the maximum number of refuels such that no two refuels among any $k$ consecutive refuels occur at stations belonging to the same chain.

Examples

Input 1

8 4 3
1 1 2 1 3 4 4 2

Output 1

5

Note 1

In this case, no two refuels among any $k = 3$ consecutive refuels can occur at stations belonging to the same chain. Five refuels can be achieved, for example, by choosing stations numbered 2, 3, 5, 6, 8, which belong to chains 1, 2, 3, 4, 2, respectively.

Subtasks