P2623 Item Selection

Xiao X believes that every problem has a polynomial-time algorithm. To prove it, he decides to be a traveling salesman once. Before setting off, Xiao X needs to choose some items to use on the road, but he only has a backpack with capacity $m$. Obviously, the knapsack problem is too easy for Xiao X, so he wants you to solve this problem for him.

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.

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 a single line containing one integer: the maximum total value that can be carried in the backpack.

- 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