P11769 Singing Practice

In 2077, the highly anticipated Tianyi v100 voicebank was released! However, getting familiar with this new voicebank is not an easy task.

Tianyi has made a practice plan spanning $n$ days. She works extremely hard, and her daily practice duration must be **monotonically non-decreasing**. Meanwhile, to protect her voice, she can practice for a **maximum** of $t_i$ units of time on the $i$-th day. The effectiveness of practice varies from day to day, influenced by factors such as weather, and we quantify the effectiveness of practice on the $i$-th day as $w_i$, indicating that every unit of time she practices on that day will increase her familiarity by $w_i$. Note that it is possible for $w_i$ to be less than $0$, meaning that perhaps due to factors like excessive heat, her practice may have a negative impact. Now, Tianyi has researched the weather forecast for the next $n$ days and estimated the values of $t_i$ and $w_i$ for each day. Please determine the maximum amount her familiarity can be improved.

N/A

N/A

### Sample Explanation She practices for $2$ units of time on the first day,increasing her familarity by $4$; She practices for $2$ units of time on the second day,increasing her familarity by $-2$ (decreasing by $2$); She practices for $3$ units of time on the third day,increasing her familarity by $3$. Tianyi's familiarity has increased by a total of 5. It can be proved that there is no way to increase her familiarity higher than $5$. ### Constraints **Subtasks Applied.** You can only gain the score of the subtask if you accepted all the tests in the subtask. |Subtask ID|$n\le$|$t_i\le$|Special Property|Score| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$10$|No|$10$| |$2$|$10$|$10^9$|No|$10$| |$3$|$100$|$100$|No|$10$| |$4$|$5000$|$5000$|No|$10$| |$5$|$5000$|$10^9$|No|$10$| |$6$|$10^5$|$10^5$|No|$10$| |$7$|$10^6$|$1$|No|$5$| |$8$|$10^6$|$10^9$|Yes|$15$| |$9$|$10^6$|$10^9$|No|$20$| Special Property: $t_i$ is uniformly randomly generated in $[0,10^9]$ For all tests, it is guaranteed that $1\le n\le10^6$，$0\le t_i\le10^9$，$-1000\le w_i\le1000$.