Description

Xiao X can choose from $n$ items, divided into three categories: A, B, and C.

1. Type A items have values that change with the volume you allocate to them. Their value follows the function $v(x) = A x^2 - B x$, where $A$ and $B$ are two parameters for each type A item. Note: for type A items, there is only one item for each volume amount.

2. Type B items have fixed value $A$ and volume $B$, and each has a parameter $C$, which is the number of copies available.

3. Type C items also have fixed value $A$ and volume $B$, but the number of copies available is unlimited.

Your task is to determine the maximum total value Xiao X can carry in his backpack.

Input Format

The first line contains two integers $n$ and $m$, the number of items and the backpack capacity.

Then follow $n$ lines, each describing one item. The first integer $x$ indicates the item category:

• If $x = 1$, it is a type A item. The next two integers $A$, $B$ are this item's two parameters.
• If $x = 2$, it is a type B item. The next three integers $A$, $B$, $C$ denote the item's value, its volume, and the number of copies available, respectively.
• If $x = 3$, it is a type C item. The next two integers $A$, $B$ denote the item's value and its volume.

Output Format

Output a single line containing one integer: the maximum total value that can be carried in the backpack.

1 0
1 1 1

0

4 10
2 1 2 1
1 1 2
3 5 2
2 200 2 3

610

Hint

• For $50\%$ of the testdata, only types B and C appear.
• For $70\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 500$, $0 \le A, B, C \le 200$.
• For $100\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 2000$, $0 \le A, B, C \le 200$.

Translated by ChatGPT 5