P11069 "QMSOI R1" Smoked Fish

Everything started with a general called Shen Xun Yu... [So where is the connection between this problem and Shen Xun Yu?](https://www.luogu.com.cn/paste/pk12x8vh)  # Background

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.

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: ~~~cpp const int M=1e9,C=1e5+5; void read(){ cin>>n>>m>>k>>s; mt19937 rand(s); for(int i=1;i

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

### 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