Buffet Lunch Optimization

You are making your lunch choices at a buffet where various dishes are available. Some dishes are discrete – they come in pieces (for example, dumplings) and you can only take an integer number of pieces – and others are continuous – for example, tzatziki – where you may take any real‐valued amount (in grams).

Each dish i is described by two parameters: an initial tastiness t_i and a rate of decay \(\Delta t_i\). For a discrete dish, the tastiness of the n^th piece is \[ t_i - (n-1)\Delta t_i, \] and the total tastiness obtained by eating N pieces is \[ \sum_{n=1}^{N} \Bigl(t_i - (n-1)\Delta t_i\Bigr)= N\,t_i - \Delta t_i \cdot \frac{(N-1)N}{2}. \] For a continuous dish, if you take X grams the tastiness is given by the integral \[ \int_{0}^{X} (t_i - x\,\Delta t_i)\,dx = t_i X - \frac{\Delta t_i}{2}X^2. \]

You have a total meal weight of w (the sum of the pieces and grams taken) and your goal is to maximize the overall tastiness. In other words, you must choose how many pieces to take from each discrete dish and how many grams from each continuous dish so that the total weight is exactly w and the total tastiness (the sum of tastiness from each dish) is maximized.

Note: For discrete dishes you cannot take a fraction of a piece. Also, if the incremental tastiness becomes non‐positive, you should not take more of that dish.

Hint: The optimal solution can be obtained by a greedy strategy where at each step you choose the "next unit" of food (either a whole piece from a discrete dish or an appropriately sized portion from a continuous dish) that gives the highest marginal tastiness. For continuous dishes the marginal tastiness decreases linearly with the amount consumed, so you can decide to take a chunk at once (by integrating the tastiness function) until its marginal tastiness falls to the level of the next best option.

inputFormat

The first line contains two numbers n and w, where n (an integer) is the number of dishes and w (a positive real number) is the total meal weight allowed.

Then follow n lines. Each of these lines describes a dish with three values:

• A character D or C indicating a discrete or continuous dish respectively.
• A real number t: the initial tastiness.
• A real number Δt: the decay rate.

You may assume that for every dish the decay rate is positive and that for discrete dishes you only take pieces when the tastiness is positive.

outputFormat

Output a single real number – the maximum total tastiness achievable – with an absolute or relative error at most 10^-6.

sample

2 5
D 10 2
C 8 1

38.000000