Building Blocks

Accepts: 105
Submissions: 1415
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
看完电影后,乐乐回家玩起了积木。
他已经搭好了$n$堆积木,他想通过调整积木,使得其中有连续$W$堆积木具有相同的高度,同时他希望高度恰好为$H$。
乐乐的积木都这了,也就是说不能添加新的积木,只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆,但是不能移动到两堆之间。比如,一次移动之后,"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算,需要移动的最少积木数。
输入描述
有多组测试数据,大约$100$组。
第一行三个整数,$n,W,H,n$表示有多少堆积木。
第二行$n$个元素,表示这$n$座积木的高度。
所有数据的范围$[1,50000]$;
输出描述
输出最少需要移动的次数,如果无法完成输出-1。
输入样例
4 3 2
1 2 3 5
4 4 4
1 2 3 4
输出样例
1
-1
Hint
样例解释:把第3座积木上的一个积木移动到第1座上,前3座积木的高度就变成了2 2 2,就得到了一个3*2(积木必须是连续的W堆)。