مالک بعد از تصاحب ثروت ریزآبادیها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن n گل در یک ردیف کاشت. هر گل بویی دارد و iامین بو از سمت چپ ai واحد بو دارد. میثم هر روز هنگام غروب خورشید، به باغش میرود و از سمت چپ به سمت راست باغ حرکت میکند. اگر به گلی برسد که بوی آن را حس نکند بسیار خشمگین میشود و تمام باغ را آتش میزند. او بوی گل i>1 را حس نمیکند اگر ai<ai−1 باشد.
مالک که از این موضوع آگاه است n تا اسپری خریده است تا هر روز صبح به گلها بزند و بوی آنها را فقط در آن روز مقداری بیشتر کند. برای اینکه بوی گل iام را یک واحد افزایش دهد، باید یک پیس از اسپری iام به آن بزند. قیمت هر پیس از اسپری iام bi تومان میباشد. گاهی اسپریها کیفیت لازم را ندارند و قیمت آنها منفی میشود! قابل ذکر است که بوی گلها نمیتواند از 106 بیشتر شود.
مالک در q روز بعدی، وقتی به باغ برود بوی یکی از گلها افزایش مییابد. در روز iام مقدار axi به اندازه yi>0 بیشتر میشود. او که بسیار پولپرست است، میخواهد با کمترین هزینه ممکن، هر روز باغ را باب میل پسرش کند. به او کمک کنید تا این هزینه را در هر روز پیدا کند.
در خط اول n و q، تعداد گلها و تعداد روزها بهترتیب میآیند.
در خط دوم n عدد a1,a2,...,an بهترتیب میآیند.
در خط سوم n عدد b1,b2,...,bn بهترتیب میآیند.
در iامین خط از q خط بعدی، دو عدد yi و xi بهترتیب میآیند.
در q خط، به ازای هر روز که مالک وارد باغ میشود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.
ورودی نمونه | خروجی نمونه |
---|---|
3 3 4 9 6 -1 3 0 3 4 1 6 3 5 | -5 3 3 |
6 3 3 1 3 2 4 4 1 -5 1 1 1 1 1 3 5 6 2 999999 | -1000008 -1000014 3999981 |
در نمونه اول، روز اول دنباله گلها ⟨4,9,10⟩ میباشد. مالک میتواند ۵ بار به اولین گل اسپری بزند و دنباله گلها ⟨9,9,10⟩ میشود و ۵- تومان خرج کند.
در روز دوم دنبال بوی گلها ⟨10,9,10⟩ میباشد. مالک میتواند یک بار به دومین گل اسپری بزند و دنباله گلها ⟨10,10,10⟩ میشود و ۳ تومان خرج کند.
در روز سوم دنباله گلها ⟨10,9,15⟩ میشود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.