U135881 导弹拦截

[1999年的导弹](https://www.luogu.com.cn/problem/P1020) $\rm{VS}$ [2010年的导弹](https://www.luogu.com.cn/problem/P1158) 这么掐指一算，又经过几年的韬光养晦，新一代导弹拦截系统即将面世。 9月27日，亚美尼亚和阿塞拜疆在纳戈尔诺—卡拉巴赫（纳卡）地区爆发新一轮冲突，造成大量人员伤亡，双方均指责对方违反停火协议，率先发动军事行动。 亚美尼亚国防部新闻发言人斯捷潘尼扬表示，阿塞拜疆军队当天对纳卡地区发动导弹攻击和炮火袭击，有两架直升机和3架无人机被击落。阿塞拜疆通讯社援引阿国防部消息说，亚美尼亚的12个防空导弹系统在战斗中被摧毁，阿方一架武装直升机被击落，机组人员幸存。 27日晚，阿塞拜疆总统阿利耶夫签署命令，鉴于纳卡接触线局势恶化，阿塞拜疆自当地时间28日0时起进入战争状态并实行局部动员，在多市实行戒严和宵禁。亚美尼亚总理帕希尼扬同日宣布，亚美尼亚进入战争状态并进行全国总动员。 纳卡地区位于阿塞拜疆西南部，居民多为亚美尼亚族人。苏联解体后，阿塞拜疆和亚美尼亚为争夺纳卡爆发战争，亚美尼亚占领了纳卡及其周围原属阿塞拜疆的部分领土。自1992年以来，在以俄、美、法为首的欧安组织明斯克小组框架内，阿塞拜疆和亚美尼亚就和平解决纳卡冲突进行了多轮谈判。1994年，两国就全面停火达成协议，但其后武装冲突时有发生。近年来，阿塞拜疆重新取得纳卡控制权的诉求越来越强烈，而亚美尼亚则希望保持现状。 纳卡地区的紧张局势引发国际社会普遍担忧。联合国秘书长古特雷斯28日分别与阿利耶夫和帕希尼扬通话，再次呼吁两国领导人立即采取措施，确保纳卡冲突地区实现停火，“在不设先决条件的情况下立即返回谈判”。欧盟外交与安全政策高级代表博雷利27日在一份声明中说，欧盟呼吁冲突双方立即停止敌对活动，严格遵守停火规定，不设前提地回归在欧安组织明斯克小组框架内的谈判。 分析认为，土耳其和俄罗斯对纳卡冲突相关方具有较大影响。土耳其和阿塞拜疆两国的主体民族语言相近，双边关系也十分密切。土耳其外交部发言人阿克索伊表示，土耳其在纳卡局势再次升级的背景下将为阿塞拜疆提供其所提出的一切援助。而亚美尼亚和俄罗斯关系紧密，双方同为集体安全条约组织和欧亚经济联盟成员。俄总统普京27日应约与帕希尼扬通电话，就纳卡地区局势进行磋商。克里姆林宫网站发表声明说，俄方对纳卡地区重现大规模武装冲突表示严重关切，当前重要任务是采取一切必要努力防止对抗进一步升级，关键是双方停止军事行动。——《人民日报》2020 年 9 月 30 日

对此，某第三方国家开发出了一款新型激光制导精准打击炸弹，用于打击地面目标。现在，有 $n$ 栋建筑排成一排，已知每栋建筑的价值为 $w_i$。 对战双方总共会进行 $k$ 次操作 - 每次可能会扔下一枚炸弹，炸弹的爆炸点在第 $p$ 栋建筑上空，攻击力为 $x$（即以该栋建筑为中心，向左右各扩展 $x$ 栋建筑会被夷为平地），制造弹体的时间为 $a$，填充燃料的时间为 $b$； - 还有可能扔下一枚燃烧弹，爆炸点在第 $p$ 栋建筑上空，攻击力为 $x$（即以该栋建筑为中心，向左右各扩展 $x$ 栋建筑的价值会减少 $x$，价值也可以是负数）； - 此外还可能对一栋建筑进行修复，即第 $p$ 栋建筑的价值增加 $v$。 当然，有一些事项必须明确： - 只有燃烧弹会导致建筑物价值减少；只有修复才能使建筑价值增加。对于炸弹，你只需要统计其造成的伤害（及所有被波及建筑的价值之和）. - 与此同时，武器资源并非无限，因此对于每一枚炸弹，需要现在机床上花费 $a$ 分钟，再填充 $b$ 分钟燃料。导弹加工的顺序与爆炸顺序无关，但必须先在机床上制造，再填充弹药。 对于每一枚爆炸的炸弹，请输出其造成的伤害；在最后，请输出所有导弹加工完成的最小时间。

无

无

### 数据范围 本题按 $Subtask$ 进行测评，只有通过全部测试点才能拿到相应分数。 | Subtask | 分值 | 时空限制 | $n\le$ | $k$ | 特殊条件 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 10 | $100\rm{ms},64\rm{MB}$ | 1000 | 1000 | 保证只有炸弹 | | 2 | 8 | $100\rm{ms},64\rm{MB}$ | 10 | 10 | - | | 3 | 22 | $100\rm{ms},64\rm{MB}$ | 1000 | 1000 | - | | 4 | 35 | $200\rm{ms},64\rm{MB}$ | $2\times10^5$ | $2\times10^5$ | - | |5 | 25 | $1000\rm{ms},64\rm{MB}$ | $1e6$ | $1e6$ | 禁止O2，可能需要一定的常数优化 | 对于 $100\%$ 的数据，$1\le n,k,x\le 10^6,1\le w_i,v_i,a_i,b_i\le 10^9,p_i\in [1,n]$。 ### 样例解释 五栋建筑初始价值为 $10,8,7,9,4$。 第一次操作使得第二栋建筑的价值增加了 $5,\operatorname{so}8\to 13$。 第二次操作使得第一到三栋建筑的价值减少 $1$，$\operatorname{so}10\ 13\ 7\to 9\ 12\ 6$。 第三次波及范围为五栋建筑，故伤害值为 $40$。 由于只有一枚炸弹，先在机床花费 $4$ 分钟，再填充 $3$ 分钟燃料，因此输出 $7$。