暂无测试数据。

在历经多通向神殿正门的台阶总共有 $n$ 级。小 G 的步长为 $m$ , 即若小G当前处在台阶 $i$ , 则他一步能够到达的位置区间为 $[ \max\{i-m , 1\} , min\{i+m , n\} ]$ , 并且每跨出一步需要消耗 $1$ 点体力。为了方便神的信徒朝拜 , 神在台阶上放置了若干个传送门 , 传送门指向指定的台阶。但由于神死去太久 , 传送门需要用 $1$ 颗能量石来激活 , 穿过传送门不需要消耗体力。现在小 G 站在第一级台阶下 , 手上有 $k$ 颗能量石。小 G 希望能够节省体力来应对神殿中的怪物 , 请你帮他计算一下 , 小 G 至少花费多少体力 , 才能达到神殿。到达第 $n$ 级台阶就算到达神殿。重艰险后 , 小 G 终于来到了被怪物占领的神殿。

输入格式

第 $1$ 行 $2$ 个数字 , 分别代表 $n$ , $m$ , $k$。

第 $2$ 行 $n$ 个数字 $t_1 \cdots t_n$ , 分别代表第 $1 \cdots n$ 级台阶上的传送门情况。若 $t_i = 0$ , 则该级台阶上没有传送门 , 若 $t_i \neq 0$ , 则该级台阶上存在一个通向第 $t_i$ 级台阶的传送门。

输出格式

一个数字 , 代表小 G 花费体力的最小值。

数据范围与约定

对于 $30\%$的数据 : $2 \leqslant n \leqslant 5 \times 10^3 , 1 \leqslant m \leqslant 20 , k \leqslant 20$

对于 $75\%$ 的数据 : $2 \leqslant n \leqslant 5 \times 10^4 , 1 \leqslant m \leqslant 20 , k \leqslant 20$

对于 $100\%$ 的数据 : $2 \leqslant n \leqslant 5 \times 10^5 , 1 \leqslant m \leqslant 20 , k \leqslant 20$

5 5 1
1 2 3 4 5

1

5 5 1
5 4 3 2 1

0