Kar Botları (Altın)#10411
Çiftlikte kış var, bu da kar demek! Çiftlik evinden ahıra giden patika, kolaylık olsun diye 1, \ldots, n olarak numaralandırılmış karo içerir ve . karo f_i fit derinliğinde bir kar tabakasıyla kaplıdır.
Çiftçi John'un çiftlik evinin bodrumunda, 1, \ldots, b olarak numaralandırılmış çift bot bulunmaktadır. Bazı çiftler diğerlerinden daha dayanıklıyken, bazıları da daha çevik hareket etmeyi sağlar. Daha açık bir ifadeyle, . çift bot, Ç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 izin verir.
Çiftçi John, yolculuğuna numaralı karodan başlar ve inekleri uyandırmak için numaralı karoya ulaşmalıdır. 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. Çiftçi John'a, hangi bot çiftleriyle bu geçişi yapabileceğini belirlemesinde yardım edin.
İlk satırda iki tam sayı ve b~(1 \le n, b \le 10^5) verilmiştir.
İkinci satırda tam sayı f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9) verilmiştir; burada f_i, . 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, . çiftle basılabilecek maksimum kar derinliğini ve . çiftteki maksimum adım uzunluğunu sırasıyla belirten s_i ve d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) sayılarını içerir.
satır yazdırın. . satırda, Çiftçi John . bot çiftiyle numaralı karodan numaralı karoya ulaşabiliyorsa , aksi takdirde olmak üzere tek bir tam sayı bulunmalıdır.
Örnek 1