Problem B: P11069 「QMSOI R1」 生熏鱼

# P11069 「QMSOI R1」 生熏鱼

## 题目背景

一切起源于一个叫神荀彧的武将...

[那这道题与神荀彧的关系在哪里呢？](https://www.luogu.com.cn/paste/pk12x8vh)


## 题目描述

一共有 $n$ 种攻击，第 $i$ 种攻击会先让你得到 $a_i$ 点经验，然后让你失去 $b_i$ 点血量。

你将**依次**受到 $k$ 次攻击，其中，第 $i$ 次攻击的种类是 $c_i$，你的初始血量为 $m$。

为了获得更多的经验，你可以选择 $n$ 种攻击中的任意种，并防止你受到的第一次这种攻击，防止后既不会损失血量，也不会增加经验值。

现在你想知道的是在你的血量降到 $0$ 及以下前，最多能获得多少点经验。

## 输入格式

一行 4 个整数，分别代表 $nmks$，其中，$s$ 为随机种子，其它变量含义与题目描述相同。

因为本题输入数据过大，选手需要使用如下方式获取数据：
~~~cpp
const int M=1e9C=1e5+5;
void read(){
    cin>>n>>m>>k>>s;
    mt19937 rand(s);
    for(int i=1;i<=n;i++)  a[i]=rand()%M+1b[i]=rand()%C+1;
    for(int i=1;i<=k;i++)  c[i]=rand()%n+1;
}
~~~

数组含义与题目描述中相同。

提示：仔细看一下数据生成方式

## 输出格式

输出一行一个整数，表示你最多能获得多少点经验。

## 输入输出样例 #1

### 输入 #1

```
2 100000 5 114514
```

### 输出 #1

```
3765807592
```

## 说明/提示

### 样例解释

样例 $1$ 的数据中 $a=\{953888980904140652\}b=\{658380624\}c=\{12112\}$。

此时显然可以不防止任何攻击或者防止第一次类型 $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 sm\le 10^9$。