Buffed Buffet

You are buying lunch at a buffet. Several dishes are available, and you can mix them freely. Some dishes, such as dumplings or roasted potatoes, come in pieces of roughly equal size. You may take an integral number of such pieces. Call these discrete dishes. Other dishes, such as tzatziki or mashed potatoes, are fluid and you may take any real-valued amount. Call these continuous dishes.

You like some dishes more than others, but how much you enjoy a dish also depends on how much of it you have already eaten. Dish $i$ has an initial tastiness $t_i$ and a decay rate $\Delta t_i$. For a discrete dish, the $n$-th piece tastes like $t_i - (n-1)\Delta t_i$. For a continuous dish, after you have already eaten $x$ grams, an additional $dx$ grams tastes like $(t_i - x\Delta t_i)\,dx$. The total tastiness from $N$ pieces of a discrete dish or $X$ grams of a continuous dish is

$\sum_{n=1}^{N} (t_i - (n-1)\Delta t_i), \quad \int_0^X (t_i - x\Delta t_i)\,dx$

Ignore pairing effects. The total tastiness of a meal is the sum of the tastinesses of its dishes, and the same rule applies to weight.

You already know every $t_i$ and $\Delta t_i$. Compute the maximum total tastiness of a meal with weight exactly $w$ grams.

A single test case is given.

• Line 1: integers $d$ and $w$ ($1 \le d \le 250$, $1 \le w \le 10000$), the number of dishes and the target meal weight in grams
• Next $d$ lines: one line per dish
  • D $w_i$ $t_i$ $\Delta t_i$: a discrete dish whose pieces weigh $w_i$ grams
  • C $t_i$ $\Delta t_i$: a continuous dish

All of $w_i$, $t_i$, and $\Delta t_i$ are integers with $1 \le w_i \le 10000$ and $0 \le t_i, \Delta t_i \le 10000$.

Print the maximum possible total tastiness of a meal with weight exactly $w$. Your answer must have absolute or relative error at most $10^{-6}$. If no meal has weight exactly $w$, print impossible.