T145827 「Beta2020」单调栈
题目描述
单调栈是一种很常用的数据结构。如果你不知道什么是单调栈，可以访问 [OI-Wiki 中的教程](https://oi-wiki.org/ds/monotonous-stack/)。
给定一个栈内元素单调递减的单调栈 $s$，其中有 $n$ 个元素。有一个 $m$ 个元素的数组，你需要在这个数组中选择**至多** $k$ 个元素（可以打乱顺序，允许不选），并将它们依次插入到单调栈中，使得最后单调栈内元素的和最大。
插入操作的伪代码如下：
```python
function insert(x):
while not s.empty() and s.top()
输入格式
第一行，三个正整数 $n,m,k$。
第二行，$n$ 个正整数，表示一开始 $s$ 中的元素。保证输入单调递减。
第三行，$m$ 个正整数，第 $i$ 个数为 $a_i$。
输出格式
一行，一个正整数，表示插入后单调栈内元素的和。
说明/提示
### 样例解释
样例一：
插入的元素依次为 $10,9,8$。可以证明这是最优的。
### 数据范围
**本题采用捆绑测试。**
| Subtask | $n,m\le$ | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ |$10$ |
| $2$ | $10^3$|$20$ |
| $3$ | $10^6$ | $70$ |
对于所有的数据，$1\le n,m\le 10^6,1\le k\le m,1\le a_i,s_i\le10^9$。