Qar çəkmələri

Fermada qışdır, bu da qar deməkdir! Fermer evindən tövləyə gedən cığır $n$ plitədən ibarətdir, rahatlıq üçün $1$-dən $n$-ə qədər nömrələnmişdir, və $i$-ci plitə f_i fut dərinliyində qar qatı ilə örtülmüşdür.

Fermer Con yoluna $1$-ci plitədən başlayır və inəkləri oyatmaq üçün $n$-ci plitəyə çatmalıdır. $1$-ci plitə fermer evinin damı altında, $n$-ci plitə isə tövlənin damı altındadır, buna görə də bu plitələrdə qar yoxdur. Lakin başqa hər hansı plitəyə addım atmaq üçün fermer Conun çəkmə geyinməsi lazımdır!

Fermer Conun pis hava üçün çantasında $1$-dən $b$-yə qədər nömrələnmiş $b$ cüt çəkmə var. Bəzi cütlər digərlərindən daha davamlıdır, bəziləri isə daha çevik hərəkət etməyə imkan verir. Dəqiq desək, $i$-ci cüt fermer Cona ən çox s_i fut dərinliyində qara addım atmağa və bir addımda ən çox d_i plitə irəli getməyə imkan verir.

Təəssüf ki, çəkmələr elə yığılıb ki, istənilən anda fermer Con üçün yalnız ən üstdəki cüt əlçatandır. Buna görə də istənilən anda fermer Con ya ən üstdəki cütü geyinə bilər (hazırda ayağında olan cütü atıb), ya da ən üstdəki cütü ata bilər (bununla da növbəti cütü əlçatan edərək).

Fermer Con çəkmələrini yalnız plitənin üzərində durarkən dəyişə bilər. Əgər bu plitədə $f$ fut dərinliyində qar qatı varsa, onda çıxardığı çəkmə DƏ, geyindiyi çəkmə DƏ ən azı $f$ fut dərinliyində qara davam gətirməlidir. Geyinmədən atdığı aralıq çəkmə cütləri bu şərti ödəməyə borclu deyil.

Fermer Cona itkiləri minimuma endirməyə kömək edin: tövləyə çatmaq üçün onun atmalı olacağı çəkmə cütlərinin minimum sayını tapın. Əvvəlcə fermer Con heç nə geyinməyib.