UVA757 钓鱼

约翰去钓鱼。他有 $h$ 小时的空闲时间，该地区有 $n$ 个湖泊，所有湖泊沿一条单向道路排列。约翰从湖泊 $1$ 出发，但可以在任意一个湖泊结束行程。他只能从一个湖泊前往下一个湖泊，但不必在每个湖泊停留。从湖泊 $i$ 到湖泊 $i+1$ 需要花费 $t_i$ 个时间单位（每个时间单位为 $5$ 分钟）。 对于每个湖泊 $i$，在最初的 $5$ 分钟内预计能钓到 $f_i$ 条鱼。此后每钓 $5$ 分钟，该湖泊预计能钓到的鱼数会减少 $d_i$。如果某个时间段预计能钓到的鱼数小于等于 $0$，则该湖泊不再有鱼可钓。 请编写程序帮助约翰规划钓鱼行程，使预计钓到的鱼总数最大化。在每个湖泊停留的时间必须是 $5$ 分钟的整数倍。 如果存在多个最优方案，选择在湖泊 $1$ 停留时间尽可能长的方案（即使某些时段不再有鱼可钓）。如果仍有并列，则选择在湖泊 $2$ 停留时间尽可能长的方案，依此类推。

输入包含多组测试数据。每组数据的格式如下： - 第一行一个整数 $n$。 - 第二行一个整数 $h$。 - 第三行 $n$ 个整数 $f_1,f_2,\dots,f_n$。 - 第四行 $n$ 个整数 $d_1,d_2,\dots,d_n$。 - 第五行 $n-1$ 个整数 $t_1,t_2,\dots,t_{n-1}$。 输入以 $n=0$ 结束。

对于每组测试数据，输出两行： - 第一行输出在每个湖泊停留的分钟数，以 `, ` 分隔（逗号后有一个空格） - 第二行输出 `Number of fish expected: ` 后跟预计钓到的鱼总数 相邻两组测试数据的输出之间用一个空行分隔。

数据范围： - $2 \le n \le 25$ - $1 \le h \le 16$ - $f_i \ge 0$ - $d_i \ge 0$ - $0 < t_i \le 192$ 由 [jiangyunuo](https://www.luogu.com.cn/user/1061050) 翻译。