题目背景

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

那这道题与神荀彧的关系在哪里呢？

题目描述

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

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

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

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

输入格式

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

因为本题输入数据过大，选手需要使用如下方式获取数据：

const int M=1e9,C=1e5+5;
void read(){
    cin>>n>>m>>k>>s;
    mt19937 rand(s);
    for(int i=1;i<=n;i++)  a[i]=rand()%M+1,b[i]=rand()%C+1;
    for(int i=1;i<=k;i++)  c[i]=rand()%n+1;
}

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

输出格式

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

2 100000 5 114514

3765807592

提示

样例解释

样例 $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$。