P11069 「QMSOI R1」 生熏鱼
题目背景
一切起源于一个叫神荀彧的武将...
[那这道题与神荀彧的关系在哪里呢？](https://www.luogu.com.cn/paste/pk12x8vh)
题目描述
一共有 $n$ 种攻击，第 $i$ 种攻击会先让你得到 $a_i$ 点经验，然后让你失去 $b_i$ 点血量。
你将**依次**受到 $k$ 次攻击，其中，第 $i$ 次攻击的种类是 $c_i$，你的初始血量为 $m$。
为了获得更多的经验，你可以选择 $n$ 种攻击中的任意种，并防止你受到的第一次这种攻击，防止后既不会损失血量，也不会增加经验值。
现在你想知道的是在你的血量降到 $0$ 及以下前，最多能获得多少点经验。
输入格式
一行 4 个整数，分别代表 $n,m,k,s$，其中，$s$ 为随机种子，其它变量含义与题目描述相同。
因为本题输入数据过大，选手需要使用如下方式获取数据：
~~~cpp
const int M=1e9,C=1e5+5;
void read(){
cin>>n>>m>>k>>s;
mt19937 rand(s);
for(int i=1;i
输出格式
输出一行一个整数，表示你最多能获得多少点经验。
说明/提示
### 样例解释
样例 $1$ 的数据中 $a=\{953888980,904140652\},b=\{6583,80624\},c=\{1,2,1,1,2\}$。
此时显然可以不防止任何攻击或者防止第一次类型 $2$ 的攻击获得 $953888980\times 3+904140652=3765807592$ 的经验值。
可以证明，不存在获得经验值更多的方案。
### 数据范围
**本题使用 subtask 进行捆绑测试**，每个 subtask 的具体分值如下：
| 子任务 | $n$ | $k$ | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $\le 10$ | $\le 10^3$ | $20$ |
| $1$ | $\le 20$ | $\le 10^7$ |$30$ |
| $2$ | $\le 24$ | $\le 2\times 10^7$ |$50$ |
对于所有数据，满足 $1\le n \le 24$，$1 \le k \le 2\times 10^7$，$1\le s,m\le 10^9$。