Coconut Canopy

View as PDF

Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

"You think you just fell out of a coconut tree? You exist in the context of all in which you live and came before you"

As a coconut farmer, your yield has been low because you have not been considering the context in which you live. Specifically, you have not been placing your coconut baskets to maximise the amount of coconuts collected.

You live on a street with n total positions, labelled 1 to n. On this street, there are m coconut trees, each of which is located at a specific position in the the street, n_i.

Rather than climbing the coconut trees, you can set up to k baskets at any position 1 to n so that it collects coconuts that fall on that position. If a coconut tree is located at n_i, then it will drop a coconut into neighbouring positions overnight, that is, a coconut will be dropped into baskets at n_i-1 and n_i +1.

Given you have k baskets, what is the maximum amount of coconuts you can collect over night?

Input Format

The first line contains 3 integers, n, m and k, the number of positions, the coconut trees and the number of baskets. (1 \le n,m,k \le 10^5) (m,k \le n)

The second line contains m integers, each with a value of n_i, describing the position of one coconut tree, these positions are distinct. (1 \le n_i \le n)

Output Format

A single integer, maximum number of coconuts that can be collected using the optimal basket choice.

Examples

Input

4 3 2
1 3 4

Output

3

Putting a basket at location 2 will collect 2 coconuts from neighbouring trees, whilst putting a coconut in location 3 will collect a coconut from the tree at location 4, giving 3 coconuts.


Comments

There are no comments at the moment.