U662012 疯狂的背包问题(15) - 泛化物品背包问题

动态规划问题中的泛化物品背包问题模板题，物品的价值随分配的体积变化而变化。

有 $N$ 个泛化物品和一个容量为 $V$ 的背包。 每个泛化物品不是一个固定的物品，而是一个函数 $f_i(x)$，表示当分配给该物品 $x$ 单位体积时，它能产生的价值为 $f_i(x)$。其中 $0 \leq x \leq V$，且 $f_i(x)$ 是一个非负整数。 你需要为每个物品分配一定的体积（可以为0），使得所有物品分配的体积之和不超过背包容量 $V$，且所有物品的价值之和最大。 求解最大价值。

第一行有两个整数 $N$ 和 $V$，用空格隔开，分别表示泛化物品个数和背包容积。 接下来有 $N$ 组数据： * 每组数据第一行有一个整数 $K_i$，表示第 $i$ 个泛化物品的取值点个数； * 每组数据接下来有 $K_i$ 行，每行有两个整数 $x_{ij}$ 和 $y_{ij}$，用空格隔开，分别表示体积和价值，即 $f_i(x_{ij}) = y_{ij}$。对于其他体积 $x$，价值 $f_i(x)$ 由这些点线性插值得到（即相邻点之间连直线）。

输出一个整数，表示最大价值。

**样例 1 解释**： 物品1的函数：f(0)=0, f(2)=3, f(5)=6，中间线性插值 物品2的函数：f(0)=0, f(3)=4，中间线性插值 最优方案：给物品1分配3体积（价值4.5，取整为4），给物品2分配2体积（价值约2.67，取整为2），总价值=4+2=6？不对，需要整数规划 更优方案：给物品1分配2体积（价值3），给物品2分配3体积（价值4），总价值=7 **注意**：由于线性插值可能产生非整数价值，所有价值都向下取整。 **数据范围** * $1 \leq N \leq 100$ * $1 \leq V \leq 100$ * $1 \leq K_i \leq 10$ * $0 \leq x_{ij} \leq V$，且 $x_{ij}$ 严格递增 * $0 \leq y_{ij} \leq 1000$