题目描述

自助餐厅里有 $n$ 种食物，分为两大类，为 “离散食物”和“连续食物”。你可以通过吃食物来获得收益。

离散食物用 $(w,t_0,\Delta t)$ 描述。对于这种食物，你只能吃整数个，每个重为 $w$。吃的第一个收益为 $t_0$，后面每吃一个收益减少 $\Delta t$。具体的，吃的第 $i$ 个这种食物 （从 $1$ 开始标号），收益为 $t_0-(i-1)\Delta t$。

连续食物用 $(t_0,\Delta t)$ 描述。对于这种食物，你可以吃任意食物的重量。如果你吃的重量为 $w$，获得的收益是 $t_0w-\dfrac{1}{2}\Delta t w^2$。

你现在要吃重量和 恰好 为 $W$ 的食物。最大化你的收益。

输入格式

第一行是 $n,W$，接下来每行先来一个字母，如果是 C 表示连续食物，后面跟两个数表示 $t_0,\Delta t$；如果是 D 表示离散食物，后面跟三个数，表示 $w,t_0,\Delta t$。

输出格式

一行一个数表示答案。相对或绝对误差不超过 $1e-6$。

2 15
D 4 10 1
C 6 1

40.500000000

3 15
D 4 10 1
C 6 1
C 9 3

49.000000000

2 19
D 4 5 1
D 6 3 2

impossible

数据规模与约定

对于 $100\%$ 的数据满足，$n\le 250,W\le 10000$。

对于离散食物，满足 $1\le w\le 10000$。

对于所有食物，满足 $0\le t_0,t\le 10000$。