Qar çəkmələri (Qızıl)#10411
Fermada qışdır, deməli — qar! Fermer evindən tövləyə gedən cığır döşəmədən ibarətdir, rahatlıq üçün 1, \ldots, n nömrələnmişdir, və -ci döşəmə f_i fut dərinliyində qar qatı ilə örtülmüşdür.
Fermer Conun fermer evinin zirzəmisində cüt çəkmə saxlanılır, 1, \ldots, b nömrələnmişdir. Bəzi cütlər digərlərindən daha davamlıdır, digərləri isə daha çevik hərəkət etməyə imkan verir. Belə ki, -ci cüt Fermer Cona dərinliyi s_i futdan çox olmayan qara addımlamağa və bir addımda d_i döşəmədən çox olmayan məsafəyə irəliləməyə imkan verir.
Fermer Con -ci döşəmədən yola çıxır və inəkləri oyatmaq üçün -ci döşəməyə çatmalıdır. -ci döşəmə fermer evinin damı altındadır, -ci döşəmə isə tövlənin damı altındadır, buna görə də bu döşəmələrdə qar yoxdur. Fermer Cona hansı cüt çəkmələrlə bu keçidi edə biləcəyini müəyyən etməkdə kömək edin.
Birinci sətirdə iki tam ədəd və b~(1 \le n, b \le 10^5) verilmişdir.
İkinci sətirdə tam ədəd f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9) verilmişdir, burada f_i — -ci döşəmədəki qarın dərinliyidir. Zəmanət verilir ki, f_1 = f_n = 0.
Növbəti sətirin hər birində iki tam ədəd verilmişdir. (i + 2)-ci sətirdə s_i və d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) ədədləri verilmişdir — müvafiq olaraq, -ci cüt çəkmə ilə addımlaya biləcəyi maksimum qar dərinliyi və -ci cüt çəkmə ilə ata biləcəyi maksimum addım uzunluğu.
sətir çap edin. -ci sətirdə bir tam ədəd olmalıdır: əgər Fermer Con -ci cüt çəkmə ilə -ci döşəmədən -ci döşəməyə çata bilirsə , əks halda .
Nümunə 1