Kar Çizmeleri#10409
Çiftlikte kış mevsimi, bu da kar demek! Çiftlik evinden ahıra giden yol, kolaylık olsun diye 'den 'e kadar numaralandırılmış karo parçasından oluşur ve numaralı karo, f_i fit derinliğinde bir kar tabakasıyla kaplıdır.
Çiftçi John yolculuğuna numaralı karodan başlar ve inekleri uyandırmak için numaralı karoya ulaşması gerekir. numaralı karo çiftlik evinin çatısı altında, numaralı karo ise ahırın çatısı altındadır, bu yüzden bu karolarda kar yoktur. Ama başka herhangi bir karoya basabilmek için Çiftçi John'un çizme giymesi gerekir!
Çiftçi John'un kötü hava sırt çantasında, 'den 'ye kadar numaralandırılmış çift çizme bulunmaktadır. Bazı çiftler diğerlerinden daha dayanıklıdır, bazıları ise daha çevik hareket etmeyi sağlar. Daha doğrusu, numaralı çift, Çiftçi John'un en fazla s_i fit derinliğindeki kara basmasına ve bir adımda en fazla d_i karo ileri gitmesine olanak tanır.
Ne yazık ki çizmeler öyle istiflenmiştir ki, herhangi bir anda Çiftçi John'un erişebileceği tek çift en üstteki çifttir. Bu nedenle, herhangi bir anda Çiftçi John ya en üstteki çizme çiftini giyebilir (o anda üzerinde olan çifti atarak) ya da en üstteki çizme çiftini atabilir (bir sonraki çifti erişilebilir hale getirerek).
Çiftçi John yalnızca bir karonun üzerinde durduğunda çizme değiştirebilir. Eğer bu karoda fit derinliğinde bir kar tabakası varsa, hem çıkardığı çizmeler HEM DE giydiği çizmeler en az fit derinliğindeki kara dayanabilmelidir. Giymeden attığı ara çizme çiftlerinin bu kısıtlamayı sağlaması gerekmez.
Çiftçi John'a kaybını en aza indirmesi için yardım edin: ahıra ulaşmak için atması gereken minimum çizme çifti sayısını belirleyin. Başlangıçta Çiftçi John'un ayağında çizme yoktur.
İlk satırda iki tam sayı ve b~(2 \le n, b \le 250) verilir. İkinci satırda tam sayı f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9) verilir; burada f_i, numaralı karodaki kar derinliğidir. f_1 = f_n = 0 olduğu garanti edilir.
Sonraki satırın her biri iki tam sayı içerir. (i + 2). satır, sırasıyla numaralı çiftle basılabilecek maksimum kar derinliğini ve numaralı çiftle atılabilecek maksimum adım uzunluğunu ifade eden s_i ve d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) sayılarını içerir.
Çizmeler yukarıdan aşağıya doğru listelenmiştir: numaralı çift, Çiftçi John'un sırt çantasındaki en üstteki çifttir, numaralı çift bir sonrakidir, ve bu şekilde devam eder.
Çiftçi John'un atması gereken minimum çizme çifti sayısını temsil eden tek bir tam sayı yazdırın. Çiftçi John'un ahıra ulaşabileceği garanti edilmektedir.
Örnek 1