A. Баавгай ба Бөөрөлзгөнө

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Баавгай өвөлд зориулж хэсэг бөөрөлзгөнө хадгалахаар шийдсэн. Тэр дараагийн $n$ өдрүүдийн нэг баррел зөгийн балтай хэдэн килограм бөөрөлзгөнө тэнцэхийг зальтайгаар мэдэж авсан. Баавгайд буй мэдээллийн дагуу $i$-р $(1 ≤ i ≤ n)$ өдөр нэг баррел зөгийн балны үнэ нь $x_{i}$ килограмм бөөрөлзгөнөтэй тэнцэхээр байна.

Харамсалтай нь баавгайд зөгийн бал болон бөөрөлзгөний аль нь ч байхгүй. Гэвч түүнд нэг баррел зөгийн балыг яг нэг өдрийн хугацаатай $c$ килограм бөөрөлзгөнөөр зээлэх найз байгаа. Энэ нь баавгай ухаалаг төлөвлөгөөтэй болох шалтгаан юм. Тэр $d$ $(1 ≤ d < n)$ өдөр нэг баррел зөгийн бал зээлээд буцаад тэр өдөртөө тухайн өдрийн үнээр зараад маргааш нь ($d + 1$ өдөр) тухайн өдрийн үнээр (түүнд өмнөх өдрийн бөөрөлзгөнөөс үлдэнэ) нэг баррел зөгийн бал аваад тэр өдөртөө найздаа зөгийн бал зээлсэн хүү болох $c$ килограм бөөрөлзгөнөтэй нь буцааж өгөх $d$ өдрийг сонгохыг хүсч байна.

Баавгай төлөвлөгөөгөө хамгийн ихдээ нэг удаа хэрэгжүүлээд ичээндээ орно. Тэр хамгийн ихдээ хэдэн килограм бөөрөлзгөнө цуглуулж чадах вэ? Хэрвээ баавгай төлөвлөгөөний явцад бөөрөлзгөнөгүй үлдвэл тэр дээрх шиг төлөвлөгөө хэрэгжүүлж чадаагүй гэсэн үг.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $c$ $(2 ≤ n ≤ 100, 0 ≤ c ≤ 100)$ байх буюу өдрийн тоо ба баавгай нэг баррел зөгийн бал зээлснийхээ төлөө өгөх бөөрөлзгөний килограмын тоо.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утгууд $x_{1}, x_{2}, ..., x_{n}$ $(0 ≤ x_{i} ≤ 100)$ байх ба $i$-р өдрийн нэг баррел зөгийн балны үнэ.

Гаралт

Бодлогын хариу болох нэг ширхэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 1
5 10 7 3 20
Гаралт
3
Оролт
6 2
100 1 10 40 10 40
Гаралт
97
Оролт
3 0
1 2 3
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр нэг баррел зөгийн балыг 3-р өдөр зээлэх ба буцаагаад 7 килограм бөөрөлзгөнөөр зарна. Маргааш нь баавгай нэг баррел зөгийн балыг 3 килограм бөөрөлзгөнөөр авч найздаа өгнө. Ингээд ашиг нь (7 - 3 - 1) = 3.

Хоёр дахь жишээн дээр 1-р өдөр нэг баррел зөгийн балаа зээлэх ба буцаагаад 100-р зарна. Баавгай 2-р өдөр нэг баррел зөгийн балаа 1-р худалдаж авна. Ингээд ашиг нь (100 - 1 - 2) = 97.

Сэтгэгдлүүдийг ачааллаж байна...