"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 total positions, labelled to . On this street, there are coconut trees, each of which is located at a specific position in the the street, .
Rather than climbing the coconut trees, you can set up to baskets at any position to so that it collects coconuts that fall on that position. If a coconut tree is located at , then it will drop a coconut into neighbouring positions overnight, that is, a coconut will be dropped into baskets at and .
Given you have baskets, what is the maximum amount of coconuts you can collect over night?
Input Format
The first line contains 3 integers, , and , the number of positions, the coconut trees and the number of baskets. () ()
The second line contains m integers, each with a value of , describing the position of one coconut tree, these positions are distinct. ()
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