Kappa's Workshop

You are given a workshop that processes raw material. Initially, the raw material has an initial weight. It then passes through a sequence of machines which may increase its weight at a cost. The workshop has two types of machines:

• Type 0: Each processing costs $v_i$ processing points and increases the material’s weight by $w_i$. This machine can be used at most once when the material passes.
• Type 1: Each processing costs $v_i$ processing points and increases the material’s weight by $w_i$. This machine can be used an unlimited number of times.

A mechanical arm is used to design the production line. Initially, there are no machines on the line and the arm is at position $0$. The machines in the line are numbered starting from $1$, and the arm’s position is always in the range $[0, u]$ if there are $u$ machines.

You are given an integer $V$, the maximum processing index (i.e. the maximum total processing points any item can spend), and $q$ commands. Let the arm’s current position be $p$ before each command. Each command is in the following format:

opt ti vi wi xi yi

Here, opt indicates the operation type, and parameters ti, vi, wi are only used in some commands. The operations are as follows:

1. Right Move: opt = 1. Update $p \gets p+1$. (Parameters ti, vi, wi are ignored.)
2. Left Move: opt = 2. Update $p \gets p-1$. (Parameters ignored.)
3. Insert Machine: opt = 3. Insert a machine after the current arm position. Its type is $t_i$, cost is $v_i$, and weight increase is $w_i$. The new machine’s position is $p+1$, and the arm remains at $p$. (Machines to the right are shifted accordingly.)
4. Delete Machine: opt = 4. Delete the machine at position $p+1$. (Parameters ti, vi, wi are ignored. Machines to the right shift left.)
5. Modify Machine: opt = 5. Modify the machine at position $p+1$, changing its parameters to $t_i$, $v_i$, and $w_i$.

After each operation, you must answer the following query:

If a material with an initial weight of $x_i$ enters the production line at the left of the first machine and passes through each machine sequentially, what is the maximum final weight it can obtain if it can spend at most $y_i$ processing points ($y_i\le V$)? If there are no machines, then the weight remains unchanged.

The processing along the line is as follows. Suppose there are $u$ machines. For each machine:

• If the machine is of Type 0, you may choose to process it at most once. Processing costs $v_i$ and increases the weight by $w_i$.
• If the machine is of Type 1, you may process it any number of times (including zero), each time costing $v_i$ and adding $w_i$ to the weight.

You need to choose the number of times to process each machine (adhering to the above limits) such that the total processing cost does not exceed $y_i$. The final weight is the initial weight plus the total additional weight accumulated from processing.

Note: All formulas are given in LaTeX format. For example, a cost is represented as $v_i$ and weight increase as $w_i$.

inputFormat

The first line contains two integers $V$ and $q$, where $V$ is the maximum processing points available for any item, and $q$ is the number of commands.

Each of the following $q$ lines contains a command in the format:

opt ti vi wi xi yi

For operations $1$, $2$, and $4$, the parameters ti, vi, and wi are ignored.

outputFormat

For each command, output one line containing a single integer: the maximum final weight of the material after processing.

sample

10 6
3 0 3 5 10 10
1 0 0 0 10 10
3 1 2 3 0 5
5 1 2 4 1 10
4 0 0 0 5 5
2 0 0 0 10 10

15
15
8
21
10
15

</p>