Background

Everything started with a general called Shen Xun Yu...

So where is the connection between this problem and Shen Xun Yu?

Background

Problem Description

There are $n$ types of attacks. The $i$-th type of attack will first give you $a_i$ experience points, and then make you lose $b_i$ health points.

You will be attacked in order for $k$ times. The type of the $i$-th attack is $c_i$. Your initial health is $m$.

To gain more experience, you may choose any one of the $n$ attack types and prevent the first attack of that chosen type from affecting you. After preventing it, you will neither lose health nor gain experience from that attack.

Now you want to know: before your health drops to $0$ or below, what is the maximum experience you can obtain.

Input Format

One line with 4 integers $n,m,k,s$, where $s$ is the random seed. The meanings of the other variables are the same as in the statement.

Because the input is too large, you must generate the data in the following way:

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;
}

The meanings of the arrays are the same as in the statement.

Output Format

Output one line with one integer, representing the maximum experience you can obtain.

2 100000 5 114514

3765807592

Hint

Sample Explanation

In sample $1$, the data are $a=\{953888980,904140652\}$, $b=\{6583,80624\}$, $c=\{1,2,1,1,2\}$.

It is clear that you can either prevent no attack, or prevent the first attack of type $2$, and obtain $953888980\times 3+904140652=3765807592$ experience points.

It can be proven that there is no strategy that yields more experience.

Constraints

This problem uses bundled testing with subtasks. The score for each subtask is as follows: | Subtask | $n$ | $k$ | Score | | :----------: | :----------: | :----------: | :----------: | | $0$ | $\le 10$ | $\le 10^3$ | $20$ | | $1$ | $\le 20$ | $\le 10^7$ | $30$ | | $2$ | $\le 24$ | $\le 2\times 10^7$ | $50$ |

For all testdata, it holds that $1\le n \le 24$, $1 \le k \le 2\times 10^7$, $1\le s,m\le 10^9$。

Translated by ChatGPT 5