5567. 水果商人
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 猫猫国的鱼干河沿岸以盛产各样式的水果， 喵喵看好此地的水果品质，决定在这里批发水果进行销售。 根据喵喵调查，鱼干河河的沿岸从左到右开始一共有 $c$ 个水果产地和 $c$ 个都市。 为了方便，我们从左到右将地点依序以产地$x$ 和都市 $x$ 标号，可以结合图一进行理解。 每个产地生产一种水果，而且互相之间生产的种类都不相同，第 $i$ 个产地可以产出 $n_i$ 颗种类 $i$ 的水果。 > 图一：上游到下游沿岸所经产地，都市一览 喵喵决定从最左边的产地 $1$ 开始由左到右每天到一个产地或都市交易。也就是说，喵喵第 $1$ 天会在产地 $1$，第 $2$ 天在产地 $2$，$\cdots⋯$，第 $c$ 天在产地 $c$，第 $c+1$ 天在都市 $1$，$\cdots⋯$，第 $2c$ 天会在都市 $c$ 交易。 喵喵在每个产地时会将当生产的 **所有** 水果买进并存放在他的船上， 而在都市时则会决定是否将船上的水果出售给此地的盘商。 由于水果有不同熟度，太生的话卖不了好价格；所以喵喵的水果从进货到贩卖至少得经过 $c$ 天 （也就是水果种类 $i$ 只能等到航行到都市 $i$ 之后才能贩卖）。 若喵喵选择在都市 $i$ 贩卖水果，他会将船上 **前** $i$ **种的所有** 水果都卸货给当地盘商并请当地盘商代为销售。 若到最右边仍在船上的水果则会被丢弃不卖（好浪费）。 假设在到达第 $i$ 个都市时船上每颗水果不限种类 **都会** 花费喵喵 $p_i$ 元的储存成本。 另外若要委托给都市 $i$ 的盘商销售水果的话还要付给当地盘商每颗水果 $s_i$ 的代销费用， 根据喵喵先前对鱼干河沿岸各地的消费状况调查，已得知在都市 $i$ 恰能卖出 $r_{i,j}$ 颗种类 $j$ 的水果。（$i \ge j$、$r_{i,j} \le n_j$） 为了决定水果的出售价格，喵喵希望能事先计算出最多卖出的水果数量。 在给出喵喵的预算 $T$，他希望你帮他决定：在这个预算内，应该要请哪些盘商代销售才能使销售水果数量最多呢？ 以下为两个 $c=3$ 的例子：例子一，若喵喵决定在都市 $1,2,3$ 贩售的话，总花费及贩售量如下： - 产地 $1$ 采购 $n_1$ 颗种类 $1$ 的水果 - 产地 $2$ 采购 $n_2$ 颗种类 $2$ 的水果 - 产地 $3$ 采购 $n_3$ 颗种类 $3$ 的水果 - 都市 $1$ 花费 $(n_1 + n_2 + n_3) \times p_1$ 的存储费、$n_1 \times s_1$ 的代售费，售出 $r_{1, 1}$ 颗种类 $1$ 的水果 - 都市 $2$ 花费 $(n_2 + n_3) \times p_2$ 的存储费、$n_2 \times s_2$ 的代售费，售出 $r_{2, 2}$ 颗种类 $2$ 的水果 - 都市 $3$ 花费 $n_3 \times p_3$ 的存储费、$n_3 \times s_3$ 的代售费，售出 $r_{3, 3}$ 颗种类 $3$ 的水果 总共销售 $r_{1,1} + r_{2,2} + r_{3,3}$ 颗水果。 > 例一：若决定在都市1，2，3卸货贩售 但如果只决定在都市 $2$ 贩售的话，总花费及贩售量如下： - 产地 $1$ 采购 $n_1$ 颗种类 $1$ 的水果 - 产地 $2$ 采购 $n_2$ 颗种类 $2$ 的水果 - 产地 $3$ 采购 $n_3$ 颗种类 $3$ 的水果 - 都市 $1$ 花费 $(n_1 + n_2 + n_3) \times p_1$ 的存储费 - 都市 $2$ 花费 $(n_1 + n_2 + n_3) \times p_2$ 的存储费、$(n_1 + n_2) \times s_2$ 的代售费，售出 $r_{2,1}$ 颗种类 $1$ 的水果及 $r_{2, 2}$ 颗种类 $2$ 的水果 - 都市 $3$ 花费 $n_3 \times p_3$ 的存储费，这些水果将被抛弃不卖 总共卖了 $r_{2,1} + r_{2,2}$ 颗水果。 > 例二：若决定在都市2卸货贩售 ## 输入格式 第一行输入两个正整数 $c, T$，分别代表产地数量和教授的花费上限 接下来一行 $c$ 个正整数 $p_i$ 表示在都市 $i$ 每颗水果的存储费用 再接下来一行 $c$ 个正整数 $s_i$ 表示都市 $i$ 的盘商代售每颗水果的费用 再接下来一行 $c$ 个正整数 $n_i$ 表示产地 $i$ 的产量 接下来 $c$ 行每行 $i$ 个数字 $r_{i,j}$，代表都市 $i$ 最多可以卖出种类 $j$ 水果的数量 $1 \le c, n_i \le 40$ $1 \le r_{i,j} \le n_j$ $1 \le T \le 10^7$ $1 \le p_i,s_i \le 1000$ ## 输出格式 在一行中输出一个整数，代表销售最多的水果数量 若预算 $T$ 不够支付任何销售方案的费用，输出 $\texttt{-1}$ ## 输入 ```in1 ... ``` ## 输出 ```out1 ... ``` ```in2 ... ``` ```out2 ... ``` ## 提示 子任务 $1$ 有 $11$ 分，满足 $c \le 20, T \le 30000$ 子任务 $2$ 有 $38$ 分，满足 $T \le 30000$ 子任务 $3$ 有 $51$ 分，无额外限制