Background

Xiao X is convinced that every problem has a polynomial-time algorithm. To prove this, he decides to become a traveling salesman himself. Before setting off, Xiao X needs to select some items for the journey, but he only has a backpack with a volume capacity of \( m \). Clearly, the knapsack problem is too simple for Xiao X, so he hopes you can help him solve this problem.

Problem Description

Xiao X has \( n \) items to choose from, divided into three categories:

1. Category A items have a value that varies with the volume allocated to them. The value \( v(x) \) of a Category A item as a function of the volume \( x \) allocated to it is given by the formula \( v(x) = A \cdot x^2 - B \cdot x \), where \( A \) and \( B \) are parameters specific to each Category A item. Note that there is only one of each volume of Category A item.

2. Category B items have a fixed value \( A \) and volume \( B \), but each Category B item has a parameter \( C \) indicating the number of this item available for selection.

3. Category C items also have a fixed value \( A \) and volume \( B \), but there are an unlimited number of each Category C item available for selection.

Your task is to determine the maximum value that Xiao X's backpack can carry for the journey.

Input Format

The first line contains two integers \( n \) and \( m \), representing the number of items and the volume of the backpack, respectively.

The next \( n \) lines describe the information of each item. The first integer \( x \) indicates the type of the item:

• If \( x \) is 1, it represents a Category A item, followed by two integers \( A \) and \( B \), which are the parameters for the Category A item.
• If \( x \) is 2, it represents a Category B item, followed by three integers \( A \), \( B \), and \( C \). \( A \) is the value of the item, \( B \) is its volume, and \( C \) is the number of this item available.
• If \( x \) is 3, it represents a Category C item, followed by two integers \( A \) and \( B \). \( A \) is the value of the item, and \( B \) is its volume.

Output Format

The output file contains a single integer, which represents the maximum value that Xiao X's backpack can carry.

Sample Input and Output

Sample Input #1

1 0
1 1 1

Sample Output #1

0

Sample Input #2

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

Sample Output #2

610

Notes

• For 50% of the test cases, only Category B and Category C items are present.
• For 70% of the test cases, \( 1 \leq n \leq 100 \), \( 1 \leq m \leq 500 \), \( 0 \leq A, B, C \leq 200 \).
• For 100% of the test cases, \( 1 \leq n \leq 100 \), \( 1 \leq m \leq 2000 \), \( 0 \leq A, B, C \leq 200 \).

见题面 Input 部分

见题面 Output 部分