Andy wants to go on a vacation to de-stress himself. Therefore he decides to take a p to an island. It is given that he has as many consecutive days as possible to rest, but he can only make one trip to the island.
Suppose that the days are numbered from 1 to N. Andy has M obligations in his
schedule, which he has already undertaken and which correspond to some specific
days. This means that the ith obligation is scheduled for day D, Andy is willing to cancel at most K of his obligations in order to take more holidays.
Your task is to find out the maximum days of vacation Andy can take by cancelling at most K of his obligations.
The first line contains an integer, N, denoting the total number of days
The next line contains an integer, M, denoting the total number of obligations
The next line contains an integer, K, denoting the largest number of obligations he could cancel
Each line i of the M subsequent lines (where 0<=i<=M) contains an integer describing Di.
1 <= N <= 10^6
1 <= M <= 210^6
1 <= K <= 210^6
1 <= D[i] <= 10^6
Here he could cancel his 3rd and 4th obligation which makes vacation length 5.
Sample input 2:
Here he could not cancel any obligation since K=0, so the vacation length is