有2个敌对的国家,A 和 B。现在他们中间有一条河。A 国和 B 国距离为 n 个单位距离,河上离 A 国距离为 i 的位置有 a_i 个浮岛。A 国有无数个士兵,所有士兵最远只能跳 m 个单位距离。每次 A 国派出一个士兵试图到达 B 国。 士兵跳上一个浮岛后,这个浮岛就会沉下去(一个浮岛沉下去后无法在被跳上)。求 A 国最多有多少个士兵可以达 到 B 国从而发起进攻。
第一行 2 个整数n, m,表示两国的距离和最大跳跃距离。
第二行 n-1 个整数 a_i ,表示离 A 国距离为 i 的浮岛数量。
一个整数,表示最多能到达 B 国的士兵的数量。
6 30 1 0 0 2
1
10 40 0 1 2 0 1 1 0 2
2
10%, 1 <= m < n <= 10,
30%, 1 <= m < n <= 1000,
100%, 1 <= m < n <= 10^6 , 0<= a_i <= 10^6