المپدیا

مالک بعد از تصاحب ثروت ریزآبادی‌ها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن $n$ گل در یک ردیف کاشت. هر گل بویی دارد و $i$امین بو از سمت چپ $a_i$ واحد بو دارد. میثم هر روز هنگام غروب خورشید، به باغش می‌رود و از سمت چپ به سمت راست باغ حرکت می‌کند. اگر به گلی برسد که بوی آن را حس نکند بسیار خشمگین می‌شود و تمام باغ را آتش می‌زند. او بوی گل $i > 1$ را حس نمی‌کند اگر $a_i < a_{i-1}$ باشد.

مالک که از این موضوع آگاه است $n$ تا اسپری خریده است تا هر روز صبح به گل‌ها بزند و بوی آن‌ها را فقط در آن روز مقداری بیشتر کند. برای اینکه بوی گل $i$ام را یک واحد افزایش دهد، باید یک پیس از اسپری $i$ام به آن بزند. قیمت هر پیس از اسپری $i$ام $b_i$ تومان می‌باشد. گاهی اسپری‌ها کیفیت لازم را ندارند و قیمت آن‌ها منفی می‌شود! قابل ذکر است که بوی گل‌ها نمی‌تواند از $10^6$ بیشتر شود.

مالک در $q$ روز بعدی، وقتی به باغ برود بوی یکی از گل‌ها افزایش می‌یابد. در روز $i$ام مقدار $a_{x_i}$ به اندازه $y_i > 0$ بیشتر می‌شود. او که بسیار پول‌پرست است، می‌خواهد با کمترین هزینه ممکن، هر روز باغ را باب میل پسرش کند. به او کمک کنید تا این هزینه را در هر روز پیدا کند.

در خط اول $n$ و $q$، تعداد گل‌ها و تعداد روزها به‌ترتیب می‌آیند.

در خط دوم $n$ عدد $a_1, a_2, ..., a_n$ به‌ترتیب می‌آیند.

در خط سوم $n$ عدد $b_1, b_2, ..., b_n$ به‌ترتیب می‌آیند.

در $i$امین خط از $q$ خط بعدی، دو عدد $y_i$ و $x_i$ به‌ترتیب می‌آیند.

در $q$ خط، به ازای هر روز که مالک وارد باغ می‌شود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.

• زیرمسئله اول (۷ نمره): $n, q \le 300$
• زیرمسئله دوم (۶ نمره): $n, q \leq 5000$ و $0 \leq b_i$
• زیرمسئله سوم (۱۹ نمره): $n, q \leq 5000$
• زیرمسئله چهارم (۲۲ نمره): $0 \leq b_i$
• زیرمسئله پنجم (۴۶ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $2 \leq n, q \leq 200\,000$
• $-10^6 \leq a_i, b_i \leq 10^6$
• $1 \leq x \leq n$
• تضمین می‌شود بوی تمامی گل‌ها هیچوقت از $10^6$ بیشتر نمی‌شود.

در نمونه اول، روز اول دنباله گل‌ها $\langle 4, 9, 10 \rangle$ می‌باشد. مالک می‌تواند ۵ بار به اولین گل اسپری بزند و دنباله گل‌ها $\langle 9, 9, 10 \rangle$ می‌شود و ۵- تومان خرج کند.

در روز دوم دنبال بوی گل‌ها $\langle 10, 9, 10 \rangle$ می‌باشد. مالک می‌تواند یک بار به دومین گل اسپری بزند و دنباله گل‌ها $\langle 10, 10, 10 \rangle$ می‌شود و ۳ تومان خرج کند.

در روز سوم دنباله گل‌ها $\langle 10, 9, 15 \rangle$ می‌شود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.

• سوال بعد
• سوال قبل