P11769 歌唱练习

2077 年，万众瞩目的天依 v100 声库发布了！ 但是要熟悉这套新声库可不是件容易的事。

天依制定了一个长为 $n$ 天的练习计划。天依十分努力，她每天的练习时长必须**单调不降**。同时，为了保护嗓子，第 $i$ 天**最多**练习 $t_i$ 个单位时间。每一天练习的效果都是不同的，受到天气等多种因素影响，我们用 $w_i$ 量化第 $i$ 天的练习效果，表示她在第 $i$ 天每练习一个单位时间会使她的熟悉度提升 $w_i$。注意 $w_i

无

无

### 样例解释 第 $1$ 天练习 $2$ 个单位时间，使熟悉度提高 $4$； 第 $2$ 天练习 $2$ 个单位时间，使熟悉度提高 $-2$（降低 $2$）； 第 $3$ 天练习 $3$ 个单位时间，使熟悉度提高 $3$。 天依的熟悉度总共提高了 $5$。 可以证明，不存在比上述方案更优的选择。 ### 数据规模与约定 **本题采用捆绑测试。** 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。 对于 $100\%$ 的数据，$1\le n\le10^6$，$0\le t_i\le10^9$，$-1000\le w_i\le1000$。 对于不同的子任务，作如下约定： |子任务编号|$n\le$|$t_i\le$|特殊性质|子任务分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$15$|$15$|无|$10$| |$2$|$15$|$10^9$|无|$10$| |$3$|$100$|$100$|无|$10$| |$4$|$5000$|$5000$|无|$10$| |$5$|$5000$|$10^9$|无|$10$| |$6$|$10^5$|$10^5$|无|$10$| |$7$|$10^6$|$1$|无|$5$| |$8$|$10^6$|$10^9$|有|$15$| |$9$|$10^6$|$10^9$|无|$20$| 特殊性质：保证 $t_i$ 在 $[0,10^9]$ 中均匀随机生成。