- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- روز ۱ دوره ۳۱
مالک بعد از تصاحب ثروت ریزآبادیها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن \(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\) به ترتیب میآیند.
\[2 \leq n, q \leq 200\,000\]
\[-10^6 \leq a_i, b_i \leq 10^6\]
\[1 \leq x \leq n\]
\[ 1 \leq y \leq 10^6\]
تضمین میشود بوی تمامی گلها هیچوقت از \(10^6\) بیشتر نمیشود.
خروجی
در \(q\) خط، به ازای هر روز که مالک وارد باغ میشود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۷ | \(n, q \le 300\) |
| ۲ | ۶ | \(n, q \leq 5000\) و \(0 \leq b_i\) |
| ۳ | ۱۹ | \(n, q \leq 5000\) |
| ۴ | ۲۲ | \(0 \leq b_i\) |
| ۵ | ۴۶ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
3 3
4 9 6
-1 3 0
3 4
1 6
3 5
خروجی نمونه ۱
-5
3
3
در نمونه اول، روز اول دنباله گلها \(\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\) میشود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.
ورودی نمونه ۲
6 3
3 1 3 2 4 4
1 -5 1 1 1 1
1 3
5 6
2 999999
خروجی نمونه ۲
-1000008
-1000014
3999981