AL09-2. Arzon zinapoya

n ta pog‘ona, i-pog‘onaga qadam qo‘yish cᵢ so‘m turadi. 0- yoki 1-pog‘onadan boshlash mumkin; bir qadamda 1 yoki 2 pog‘ona chiqiladi. Maqsad — oxirgi pog‘onadan keyingi tepa. Eng kam xarajatni toping.

dp[i] — i-o‘ringa chiqishning eng arzon narxi.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida n ta narx.

Chiqish ma’lumotlari

Eng kam xarajat.

Cheklovlar

2 ≤ n ≤ 2·10⁵, 0 ≤ cᵢ ≤ 10⁴