U125078 JZOI 1397. 圆环取数【推荐】

小K攒足了路费来到了教主所在的宫殿门前，但是当小K要进去的时候，却发现了要与教主守护者进行一个特殊的游戏，只有取到了最大值才能进去Orz教主……

　　守护者拿出被划分为$n$个格子的一个圆环，每个格子上都有一个正整数，并且定义两个格子的距离为两个格子之间的格子数的最小值。环的圆心处固定了一个指针，一开始指向了圆环上的某一个格子，你可以取下指针所指的那个格子里的数以及与这个格子距离小于$k$的格子的数，取一个数的代价即这个数的值。指针是可以转动的，每次转动可以将指针由一个格子转向其相邻的格子，且代价为圆环上还剩下的数的最大值。 　　现在对于给定的圆环和$k$，求将所有数取完所有数的最小代价。

　　输入文件的第$1$行有两个正整数$n$和$k$，描述了圆环上的格子数与取数的范围。 　　第$2$行有$n$个正整数，按顺时针方向描述了圆环上每个格子上的数，且指针一开始指向了第$1$个数字所在的格子。 　　所有整数之间用一个空格隔开，且不超过$10000$。

输出文件仅包括$1$个整数，为取完所有数的最小代价。

对于$20\%$的数据，$n≤10，k≤3$； 对于$40\%$的数据，$n≤100，k≤10$； 对于$60\%$的数据，$n≤500，k≤20$； 对于$100\%$的数据，$n≤2000，k≤500$； ### 样例解释 如图所示  ### 如何AC #### [题解](https://www.cnblogs.com/wondering-world/p/13454539.html)