302619: CF508C. Anya and Ghosts
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Anya and Ghosts
题目描述
Anya loves to watch horror movies. In the best traditions of horror, she will be visited by $ m $ ghosts tonight. Anya has lots of candles prepared for the visits, each candle can produce light for exactly $ t $ seconds. It takes the girl one second to light one candle. More formally, Anya can spend one second to light one candle, then this candle burns for exactly $ t $ seconds and then goes out and can no longer be used. For each of the $ m $ ghosts Anya knows the time at which it comes: the $ i $ -th visit will happen $ w_{i} $ seconds after midnight, all $ w_{i} $ 's are distinct. Each visit lasts exactly one second. What is the minimum number of candles Anya should use so that during each visit, at least $ r $ candles are burning? Anya can start to light a candle at any time that is integer number of seconds from midnight, possibly, at the time before midnight. That means, she can start to light a candle integer number of seconds before midnight or integer number of seconds after a midnight, or in other words in any integer moment of time.输入输出格式
输入格式
The first line contains three integers $ m $ , $ t $ , $ r $ ( $ 1<=m,t,r<=300 $ ), representing the number of ghosts to visit Anya, the duration of a candle's burning and the minimum number of candles that should burn during each visit. The next line contains $ m $ space-separated numbers $ w_{i} $ ( $ 1<=i<=m $ , $ 1<=w_{i}<=300 $ ), the $ i $ -th of them repesents at what second after the midnight the $ i $ -th ghost will come. All $ w_{i} $ 's are distinct, they follow in the strictly increasing order.
输出格式
If it is possible to make at least $ r $ candles burn during each visit, then print the minimum number of candles that Anya needs to light for that. If that is impossible, print $ -1 $ .
输入输出样例
输入样例 #1
1 8 3
10
输出样例 #1
3
输入样例 #2
2 10 1
5 8
输出样例 #2
1
输入样例 #3
1 1 3
10
输出样例 #3
-1