Knapsack Optimization with Three Item Types

You are given a knapsack with an integer capacity V and n items. The items are divided into three types: Type A, Type B, and Type C.

Type A items (甲类): For a Type A item, you can decide to allocate any integer volume x (where 0 \le x \le V) to it. Its value is given by the quadratic function

[ v(x) = A \cdot x^2 - B \cdot x, ]

where A and B are parameters unique to that item. Note that for each Type A item, you choose exactly one x (and each chosen volume option can be used at most once).

Type B items (乙类): Each Type B item has a fixed volume and a fixed value. Specifically, each such item consumes B volume and provides A value. Additionally, there is a parameter C that denotes the maximum number of copies available for that item.

Type C items (丙类): Each Type C item also has a fixed volume and a fixed value (parameters B and A respectively). However, you have an unlimited number of copies of each Type C item.

The input begins with two integers n and V --- the number of available items and the capacity of the knapsack, respectively. Each of the following n lines describes an item. The first token of each line is a character which can be:

• A for a Type A item. This is followed by two integers representing the parameters A and B in the value function.
• B for a Type B item. This is followed by three integers: the value A, the volume B, and the maximum count C.
• C for a Type C item. This is followed by two integers: the value A and the volume B.

Your task is to determine the maximum total value that can be achieved without exceeding the knapsack capacity. You may choose at most one allocation for each Type A item (by picking an appropriate x), at most the given count for each Type B item, and an unlimited number of copies for each Type C item.

inputFormat

The first line contains two integers n and V (1 \le n, V \le 1000) denoting the number of items and the knapsack capacity, respectively.

Then, n lines follow. Each line starts with a character that represents the type of the item:

• If the line begins with A (Type A), it is followed by two integers A and B (the parameters for the quadratic value function: \(v(x)=A\,x^2-B\,x\)).
• If the line begins with B (Type B), it is followed by three integers: A (value), B (volume), and C (the maximum number available).
• If the line begins with C (Type C), it is followed by two integers: A (value) and B (volume). There is an unlimited supply of this item.

All numbers are space-separated.

outputFormat

Output a single integer: the maximum total value that can be achieved without exceeding the knapsack capacity.

sample

3 10
A 1 1
B 10 5 1
C 3 2

90