يبني Farmer Ron في Colorado منتجع تزلج لأبقاره، والميزانية تسمح بمصعد واحد. خط أحادي يصل دعامة البداية الخرسانية بالنهاية عبر دعامات وسطية، ارتفاع كل منها0 فوق الأرض. فولاذ مستقيم يصل كل زوج متجاور ويجب أن يكون فوق الأرض في كل نقطة.

FR مقتصد يريد أقل دعامات. مسح $N$ قطع أرض متساوية $(2 \le N \le 5,000)$ وسجل ارتفاعًا صحيحًا $H$ $(0 \le H \le 1,000,000,000)$. السلامة تفرض مسافة متجاورة لا تزيد عن $K$ وحدات $(1 \le K \le N - 1)$. الفولاذ صلب مستقيم.

جد أقل دعامات: الفولاذ كله فوق الأرض أو مماس لها، المسافة الأفقية المتجاورة لا تزيد عن $K$، ودعامتان في أول وآخر قطعة.

الإدخال

• السطر $1$: عددان صحيحان بفراغ $N$ و$K$.
• الأسطر $2..N+1$: السطر $i+1$ يحوي ارتفاعًا صحيحًا للقطعة $i$.

الإخراج

• السطر $1$: عدد صحيح، أقل أبراج تحقق الشروط.

أمثلة

الإدخال 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

الإخراج 1

5

ملاحظة

5 دعامات في1 و5 و7 و9 و13. الفولاذ مماس في4 مواضع:1–5 و5–7 و7–9 و12–13.

4 دعامات في1 و5 و9 و13 تجعل الفولاذ تحت الأرض5–9. في1 و7 و13 يبقى فوقها لكن7 و13 يبعدان أفقيًا أكثر من4. لا حل بأقل من5 دعامات ومسافات متجاورة لا تتجاوز4.

مصدر النص الأصلي: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

مؤلف المسألة: Adam Rosenfield, 2004